MegaMan X Maverick Hunters is a classic side-scroller (and quite challenging).
Metal Slug Anthology has 5 (or 6?) of the Metal Slug arcade games rolled into one UMD. The graphics are 2D, just like the arcade versions, but the gameplay is great.
Castlevania Dracula X Chronicles is good as well. 3D version of one of the old CV games.
And I can't forget Patapon

. Rhythm-based sidescroller with unique (if a little, some may say, minimalistic) graphics and incredibly catchy music.
Check out reviews and see if any of these are what you're lookin for.