The Neo Geo Pocket Color is entirely backwards compatible with Neo Geo Pocket games, but most people don't realize that if you REALLY can't get your hands on a NGPC, the Neo Geo Pocket could play any color game, just not in color.
Big Bang Pro Wrestling
A pretty neat wrestling game. It's no Saturday Night Slam Masters, but honestly, it's probably the closest you'll get to it on a retro portable. Has a variety of wrestlers with different skills and intros. It's a bit challenging to learn, but once you get the gameplay down, there's much rumbling and many good times to be had.
Customize your mech, go through randomly generated dungeons to kill critters and find loot, fight in contests. A bit basic compared to later games of the "customizable robot" genres, but the large amount of customization to be found in this early entry is admirable and makes it worth trying out.
Bust A Move! Pocket
It's a portable Bust A Move/Puzzle Bobble. There's really not much else you need to know. tons and tons and tons of fun to be had, every time.
Cotton: Fantastic Night Dreams
Shoot 'Em Up
A horizontal cute 'em up that features a cute witch in a pretty twisted world on a search for candy. Features a variable weapon upgrade system (Kicking ass lets you kick more, while sucking means you'll likely get your ass kicked), and is a pretty close port, despite being scaled down a bit. Kinda hard, but fun.
Dark Arms: Beast Buster 1999
A curious arcade-esque action-RPG. Your character never once levels up, but can collect power-ups in stages. What does level up are your weapons. Capture enemy souls, feed them to your weapons, and evolve them into a variety of cool and twisted things, including, but not limited to: a machine gun that covers your body in steel, tentacle arms, laser cannons, and exploding dolls. You can also change your weapon's affinity, which affects damage done to elemental foes. The day/night cycle also affects your exploration, opening and closing different paths. It's only flaw is it's short. Definitely give it a shot though.
Evolution: Eternal Dungeons
A port of the Dreamcast RPG. Outside of graphics and music being scaled down a bit, town exploration limited to menus, and the lack of jumping, damn near EVERYTHING from that game can be found in here. The dungeons are still all randomly generated, the battle system works exactly the same, and Cyframe customization is still as neat as ever. If you can't find the Dreamcast version, you'll essentially get the full game (sans any fancy flashiness) in this port. Highly recommended.
A tactics game that has every single action you do revolve around strategy and commands, even turning in a different direction. Despite sounding lame on paper, it actually works quite well. If you're a fan of mecha series, you might also enjoy the atmosphere conveyed in here, which is highly reminiscent of said material.
A humorous all girl showdown between rough-and-tumble gals from various SNK games. The character selection is a bit small, but you can change some of their properties by equipping different accessories. Everything is well animated, featuring many send-ups of the character's original attacks (though still just as effective). The music's great, and the control is spot on. The big draw here is the option to change game speed, allowing some insanely fast-moving fights, which is loads of fun as a result.
King of Fighters R-2
A sort of psuedo-port of King of Fighters '98. Features far less characters, but has a number of alternate versions for most fighters, which is cool if you're in the technical know. The big draw here is the "Making Mode" feature, which is an RPG-esque take on the game, with equipable abilities, and various challenges to face.
The Last Blade
The original Last Blade games were well-loved for their incredible gameplay, and were a shining example among fighting games. Amazingly, none of that great gameplay has been lost in this port. Features spectacular graphics for the NGPC, well done music transitions, and a pretty good cast of characters. One really cool factor is that the game seems like an LB1 port, but as you progress with various fighters, a number of things change in-game, leaving you with a hybrid of LB 1 and 2. This is a great game to have, even if you've played LB1+2, since there are some roster variations as well. What Match of the Millenium is for many great characters, Last Blade is for great gameplay.
Metal Slug: 2nd Mission
Run 'N Gun
Features various weapons, vehicles, music, and gigantic bosses you'd come to expect from the Metal Slug series. However, there are a number of interesting aspects added as well. Stages aren't entirely linear for one, occaisonally you'll have to do some sneaking missions with a knife only, and each character has a slightly different mission set. While slower stages in a fast paced franchise may sound weird, it works really well. Definitely one of the best entries for the NGPC.
Ogre Battle Gaiden: The Prince of Zenobia
A side story to the Ogre Battle series. Features that Ogre Battle gameplay you love, and is also a bit long as well. It's only in Japanese though.
"Picture Puzzle" my ass. This is Picross. Make pictures by filling in the proper spaces.
Puzzle Link 1
This is a quirky puzzle game. It has you shooting bridge pieces to connect different parts in order to clear the stage to get cards of weird monsters. It sounds weird and complicated, but it's actually quite easy and nice fun as well. It gets damn hard on later levels though, so beware. Curiously, the monster cards are kind of funny.
Puzzle Link 2
If you liked the first, here's some more. More stages, more shooting, more funny little monster cards.
Rockman Battle & Fighters
Contains pretty good ports of Megaman Power Battle and Megaman Power Fighters. For those not in the know, it's like normal Megaman, but with boss fights only (sort of making it into a fighting game), and much more action packed.
Samurai Shodown! 2
A pretty good transition of classsic SS action, now cute-ified.
SNK Vs Capcom: Card Fighters Clash (Capcom/SNK Versions)
Hands down one of the best card games of all time. It's most similar to Yu-gi-oh, but with far less bullshit and far more balanced. The only truly restricted elements are duplicates (only up to 3 of any card in your deck) and SP needed to use Action cards (like spell cards, they help you or hurt your enemy). Chara-cards may also have special abilities which simulate Action cards and other effects as well. In addition to that, you can dump up to 3 cards into one chara-card (depending on the card) to power it up further (Example: Marco, Fio, Eri, Tarma). There's a whole lot to see and do here, even post-game. The differences between the two are minimal, with some cards changed up exclusive or hard to find on one versus the other (unless you trade). In short, just choose the one you like, and start collecting and fighting. You don't need to be a hardcore fan of SNK or Capcom to enjoy this, but you may miss out on several of the references made.
Pretty much more of the same that the first game gave you. A new element added is Reaction cards, which act like Yu-Gi-Oh's trap cards, and also require SP. This one lacks abit of the magic the first had, mostly because the RPG-like world of the first is downplayed and there's far less references, but in the end, it's still a good successor to it.
STAY THE FUCK AWAY FROM THE DS GAME THOUGH.
SNK Vs Capcom - Match Of The Millennium
This is why many people owned an NGPC. Outside of the spot-on fighting with different super-mode settings from Capcom and KoF, there's the cool "olympic" mode. This includes a few mini-games based on a few Capcom and SNK characters and also some fighting-based challenges. The purpose of these is to gain points which unlock new super-attacks for your characters. The sheer combination of characters, stages, music, and bonuses from so many games is enough to make any fighting fanatic salivate. If you've never played a fighting game before, this one would be a great start.
Sonic the Hedgehog - Pocket Adventure
Pretty much a port of Sonic 2 with some music from Sonic 3 added in. The game controls quite well, and the music sounds pretty good, too.