Gimmick my freakin ass
Fallout, given your new Spitfire game project you should check out Glory Days 2, it's a bit like classic choplifter but with a whole army to support you, becomes quite tactical.
I can't just throw a few suggestions into a paragraph, so I'm gonna break it down by genre.
Racing:
*Ridge Racer DS is quite good, nice arcadey feel to it that seems to work on the DS better than other racers.
*MarioKart DS, it's a must, it's the best racer you can buy, and multiplayer is an absolute riot.
FPS:
*Metroid, your probably aware of this already, but it's probably going quite cheap second hand, and even if FPS is not your favourite genre you should own it. FPS games on the DS can be as good as this.
*CoD4, this impressed the hell out of me, it actually makes Brothers in Arms appear quite clunky, a really nice effort and some great visuals as well. Just remember to go for headshots as the enemies seem to need a lot of lead before they fall over.
Shooters:
*Nanostray, it's a really pretty, Japanese style vertical scroller with 3D graphics but is purely top down, classic gameplay, but brutally difficult. If you like a real challenge then Nanostray will keep you occupied.
*Geometry Wars Galaxies, the best shooter I've ever played on the DS, has great tracker style music, some insance visuals, but it's just a crazy retro shooter that keeps you thinking the whole time. The 360 version is mindlessly dull in comparison.
Retro:
*Namco Museum, Galaga, Galaxian, PacMan - all classics if you like these games then this is a must buy, my favourite aspect of this though is the new multiplayer PacMan. It allows upto 4 players to take turns being pacman, while the other 3 play as ghosts, trying to kill pacman so they can become him. It's quite a novel way to play it, has an extra 3D screen and a less retro feel - classic pacman is included though.
*Konami Arcade Classics, it's my favourite retro cart, has things like Nemesis, Track and Field, Russian Attack, Time Pilot and Contra. There's enough gameplay on that little cartridge to kill a goat. You can even mess around with the motherboard jumper settings to give yourself more lives and stuff. Like walking round with a dozen classic arcade cabinets in your pocket.
Adventure:
*Room 215, I tend not to go for these games, and honestly when I first started playing it I was not overly impressed. Once I got into it and gave it a real chance though it was great, really novel uses of the touch screen, like making jigsaw, then to see a message printed on the other side, you have to close the DS screen to flip it over. These games are becoming a modern equivalent of a bedtime detective novel, well worth looking into if you want something mellow to play. You can get Myst for the DS now as well, but I've yet to play that, the DS is getting a decent library of these types of games.
Gambling:
*Sega Casino, Most people are just looking to play things like Roulette and Texas Hold'em, which is why this cart is so good - the implimentations are very basic looking, no fancy 3D avatars, just straightforward games that have a nice flow to them. I've played most of the Texas Holdem games and they all try to squeeze the DS for 3D graphics, which drag the game down because it makes them too slow. Sega Casino let's you get right into the game, fast and snappy, the way hold'em should be.
Strategy:
*Advance Wars, there's actually a new Advance Wars game coming to DS soon, so I'd suggest waiting on that - but these are the best strategy games by far, the others tend to try to do too much, this is as action packed as turn based strategy can get - disappointed with the multiplayer, but the campaign is simply great.
*Warhammer 40k, turn based again, but more like UFO, or Laser Squad, haven't played it much to be honest, but it seems like the sort of game you might be into - I think you like UFO if I'm not mistaken.