2nd Mission rocks. It's also cool to hear so much of the music of X and 3 remixed to work with the pocket hardware. But it definitely has a lot of replay value. Parts of it are modeled a bit like the extras thrown in the Playstation port of Metal Slug X, like the whole Training Camp bit. Though you are limited to Time Attack stuff outside the main game, there's no special hidden level scenarios. However, the branching paths of 2nd Mission add a lot of replay to the title, with some levels being kind of tricky to get to. The hostage rescue idea also works out nice and you can view the hostages to get messages from them. They may let you know how many hostages are on a level in total, give you hints as to where you might find more, reveal a clue for hidden stuff. Not all hostages will. Some will just thank you. You raise in rank with rescues and such and you can see that reflected when you go back to the training camp (which keeps track of your progress).
I only have 1 2nd Mission, though. However, I think I know a place that can help you out with NGPC games. Including 2nd Mission.
http://www.e-cdrom.com/video-games-neogeo.html
Prices seem decent here. However, none of the real rare titles, though.
Fortunately, you have it easy with Sonic. Mainly since that was redistributed to the states in the 4-pack for NGPC(what I call, the best 4-pack portable game collection money can buy). Every EB should have a copy. Or if you just want the cart by itself with no other packaging but the clamshell itself, NCS sells it for only 6 bucks. The only somewhat expensive NGPC cart they have in stock is Super Real Mahjong, special edition