Adventure Time: Hey Ice King Why'd You Steal Our Garbage !? --- If you're a fan of the show then you NEED to get this game. It's pretty fun and the music is great, especially Marceline's theme.
Pushmo/ Pullbox: If you're wanting to play a good puzzle game then I would really recommend this one. You can also create your own Pushmo and share them with people/ Download other people's Pushmo with QR codes.
Cave Story: Its a really solid 2D, sidescrolling jump and shoot. Also has great music
Ghost Recon: Shadow Wars: This one is a top down view, turn based strategy game. It starts out pretty easy but gets pretty challenging later on. Based on what you said you were into I'd recomend this one the most
Kid Icarus: Uprising: Totally worth the 25-year wait. Hell, Hades' dialogue alone makes it worth the price. Mario Kart 7: Because Mario Kart. Resident Evil: Revelations. Proof that Capcom can still put out a good horror game, which makes RE6 even more disappointing. Paper Mario Sticker Star: Because Paper Mario. Metal Gear Solid 3: MGS3 is one of the better MGS games, and now it's on 3DS with updated controls and camera! Ocarina of Time 3D
Professor Layton and the Mask of Miracles, and the new Pokemon Mystery Dungeon game that's coming out early next year. I haven't had a chance to play either of them yet, but Professor Layton and PMD are two of my favourite DS series and I would highly recommend them. All the games so far have had above-average plots (Explorers of Time/Darkness/Sky and the first three Layton games stand out especially) and are very well-rounded games. Unless both games have suddenly taken a turn for the much worse, then they'll be well worth playing.
Kid Icarus Uprising is something you should DEFINITELY get. It's phenomenal! The plot twists, the battle sequences, the characters, styles...just amazing. And the voice acting cutscenes? Brilliant.
Mario Kart 7 is a must because...well...it's a racing game! It's great for when you're bored or if you feel like going head to head with WiFi (or wireless) competition! Plus the customization is super cool.
I just got Kingdom Hearts Dream Drop distance and I'm loving it to pieces. Simply epic. It's a series of awesome. Best of all, you don't even have to be lost or go online to read what the series is about. As you play, you're filled in on previous game plots you missed. Battles are refreshingly challenging, plot is thick with tension, tons of references (anyone for Tron?)
Animal Crossing 3DS should be coming out in spring. I'm a huge follower since I was little so I like the series. A break from your battles and competition. Exchange those keyblades & race karts for becoming mayor and building a town.
And then it won't be for awhile but Super Smash Bros 4 will be for 3DS. And rumor has it Hey You Pikachu's being remade for the system as well.
The only ones that comes to mind that you might like:
Shin Megami Tensei: Devil Survivor Overclocked: a deep and hardcore tactical rpg with a great amount of non-linearity in Pokemon-like gameplay and story. Zero Escape: Virtue's Last Reward: a horror adventure game that's also non-linear but has a thoughtful story and puzzles are good as well.
Pardon, but I feel it's only fair to mention something about Kid Icarus. It was HEAVILY criticized for it's controls. You can blame Nintendo for the 3DS's design on that one. HAL was very smart in allowing full customization for them though, so if you do purchase it, fiddle with the options before heavy play.
Not mentioning ports, shovelware, or rehashes... Heroes of Ruin is an excellent RPG (by Square Enix of all people I believe), Kingdom Hearts is surprisingly really good, Pokemanz Black or White 2 is a normal DS game, but it does use 3DS features. Adventure Time is very well done but I think that may be considered a rip off for some.
Those are some good adventure and RPG titles. Go for Heroes.
Tales of the Abyss got a 3DS rerelease and is awesome. Also Legend of Zelda: Ocarina of Time. I heard Kingdom Hearts is good, but I don't really like Kingdom Hearts and so haven't played it and therefore can't really recommend it. Your call on that one.
I just recently got a game called Kid Icarus: Uprising. It's an adventure game where you play as Pit, and you get to fight underworld creatures in order to stop Medusa. There are some flying shooter elements, as well as you can change your weapon sets. It also comes with a set of AR cards that you can battle with, but I haven't figured it out yet.