So I got a good deal on New 3DS XL so I bought one. Mostly for the wife because I am not that much in to handheld but still I want to try it out. With that said, what games are the must haves? I havnt played a single handheld game since the GBA days so both DS and 3DS libraries are totally unknown to me.

What 10 DS games and what 10 3DS games should I get? Platformers, RPG, Shmups, Adventure are prefered genres but I am willing to explore other categories as well if the game are great enough =) You could exclude all the Zelda games because I am going to buy them regardless.

3DS
Fire Emblem Awakening
Bravely Default
Shin Megami Tensei IV
Kid Icarus Uprising
Pokemon X/Y and or ORAS
Monster Hunter 4 Ultimate

These are just some that I have that I think are musts.

DS

Final Fantasy IV

Final Fantasy Tactics A2 Grimmiore of the Rift

Fire Emblem Shadow Dragon

Pokemon Diamond/Pearl/Platinum and or Black/White/Black2/White2

Golden Sun Dark Dawn 

Main Pokemon games are a given. As for the rest:

DS

-New Super Mario Bros
-Pokemon Mystery Dungeon: Explorers of Time/Darkness
-Might & Magic: Clash Of Heroes
-9 hours 9 doors 9 persons
-The World Ends With You
-GTA Chinatown
-Chrono Trigger
-Sonic Rush
-Megaman Zero collection
-Megaman ZX/ZX Advent

3DS

-Fire Emblem: Awakening
-Etrian Odyssey Untold. The Milennium Girl
-Kid Icarus: Uprising
-Kirby Triple Deluxe
-Bravely Default
-Super Mario 3D Land
-Zero Escape: Virtue's Last Reward
-Mario Kart 7
-SMT Devil Survivor Overclocked
-Resident Evil Revelations

Good luck finding some of this, because they are pretty rare/expensive.

For DS:

Radiant Historia
Golden Sun: Dark Dawn
Etrian Odyssey 1,2,3
Mario & Luigi 2,3
any and all Dragon Quest + Final Fantasy games.

alright here we go, DS: New super mario bros, Mario kart DS, Pokemon Platinum, Pokemon heartgold or soulsilver, pokemon black 2 or white 2, Legend of zelda spirit tracks, Phantom hourglass is good too but some people say they dont like it, so its up to you, Maybe a professor layton game, cant come up with more DS games. 

3DS: KID ICARUS UPRISING,Fire emblem awakening, Legend of zelda a link between worlds, Legend of zelda ocarina of time 3D, legend of zelda majoras mask 3D, Pokemon X or Y, pokemon Omega ruby or alpha sapphire, mario kart 7, Super mario 3D land, Kirby triple deluxe, Mario and luigi dream team, Super smash bros 3DS, upcoming Fire emblem fates probably

Everyone's mentioned what I would have, so I'll be original and say you should buy Shin Megami Tensei: Strange Journey on the DS. Kinda rare nowadays though

Damn, a lot has happened since GBA. I too skimmed through the DS library but 3DS is my main right now. I might not be able to shoot 10 DS games right now.

DS:

Super Mario 64 DS(Platformer), The World Ends With You(JRPG), Dragon Quest IX(JRPG), Pokemon Diamond/Pearl(JRPG), Pokemon Black/White (If you don't get enough Pokemon, they made a Black/White 2 as well), Mario Kart DS(Kart Racer), New Super Mario Bros.(Platformer), Professor Layton is kind of a RPG/Puzzle game. It's different and that's what I liked about it.

3DS:

Super Mario 3D Land (Platformer), Pokemon X&Y(JRPG), Fire Emblem Awakening(Strategy RPG), Mario Kart 7, Pokemon Omega Ruby/Alpha Sapphire(JRPG), Kid Icarus Uprising(On Rails Shooter/Action/Adventure/RPG/everything), Bravely Default(JRPG), Mario & Luigi Dream Team (JRPG), Shin Megami Tensei IV (JRPG), Kirby Triple Deluxe (Platformer), Star Fox 64 3D (On Rails Shooter)

I know, most of these are Nintendo games but to tell you the truth, they are all really great games and you shouldn't miss em. It is actually a crime to only be able to recommend 10 games. I hope you enjoy your new console, it will keep you busy for a while.

3DS
Pokémon X & Y
Pokémon OR & AS
Mario Kart 7
Kid Icarus: Uprising
Donkey Kong Country Returns 3D
Super Smash Bros for 3DS
Star Fox 64 3D
Super Mario 3D Land

> excluded Zelda titles because you're already going to buy them

DS
Pokémon Black & White
Pokémon Black & White 2
Trauma Center: Under the Knife
Trauma Center: Under the Knife 2
Mario Kart DS
Pokémon Ranger (the first one)

My list really depends on what you like but I edited it a bit to make it more general, could be better, but oh well..

NDS
The World Ends With You
Rune Factory 3
Fire Emblem: Shin Monshou no Nazo ~Hikari to Kage no Eiyuu~
Disgaea DS
Final Fantasy III/IV
Dragon Quest IX: Sentinels of the Starry Sky
Golden Sun: Dark Dawn
New Super Mario Bros
Pokemon Platinum/ HGSS
10. Mario Kart DS

3DS
Fire Emblem Awakening
Rune Factory 4
Fantasy Life
Theatrhythm Final Fantasy / Curtain Call
Super Smash Bros for 3DS
Tales of the Abyss
Animal Crossing New Leaf
Pokemon XY/ORAS
The Legend of Zelda: Ocarina of Time/ Majora's Mask 3D
Mario Kart 7

3DS:

Super Mario 3D Land
Mario Kart 7
The Legend of Zelda: Ocarina of Time 3D
The Legend of Zelda: Majora's Mask 3D
The Legend of Zelda: A Link Between Worlds
Pokemon X/Y
Fire Emblem Awakening
Kid Icarus: Uprising
Super Smash Bros. for Nintendo 3DS
Bravely Default

Since we're also talking about the New 3DS, don't forget about Xenoblade Chronicles.