welcome to the Pocket... I love it.
All good starting titles have been mentioned I guess, except maybe Dark Arms - still cheap to be had, nice atmosphere and concept.
Dark Arms was great, I loved the gothic feel of everything.
My favs are Metal Slug (1 and 2), Dark Arms, Neo Turf Masters, and Card fighters. Faselei and Gals fighters are pretty well regarded, but those are pricey these days.