Katamari Damacy’s multiplayer mode is only decent, sadly - there’s only one arena and it’s somewhat limited in size. However, it’s still an awesome social experience because it’s so quirky that even the most non-gamer of non-gamer friends will want to play it.
VF4:EVO is the best singleplayer game I’ve ever played, but it’s not good if you want something to play with friends, unless they all happen to be VF4:EVO fanatics as well. I’d recommend Soul Calibur 2 or Guilty Gear X2 instead when it comes to fighting games - they’re more “attractive” (SC2 has flashier graphics/sound, GGX2 is absurdly wacky but in a legitimately funny way) and they’re much easier to become at least adequately good at, while still being tough and satisfying to master.
Frequency and Amplitude are pretty good rhythm games, and while Amplitude might still be relatively expensive, I’m sure you can get Frequency for very little money. Also, if you’re one of the anti-mainstream-music types, you’ll like Frequency’s much more obscure soundtrack better.
Wrestling titles make for great multiplayer games. The AI usually sucks, which drags down the singleplayer experience, but clever human players can make any match challenging. Having said that, Def Jam:Fight For New York is the most brutal game of this type - not in the sense that it’s overly bloody/gory, but rather because the viciousness of the various moves will make you wince. The attacks look and sound like you’re actually putting the fucking HURT on someone.
WWE’s Smackdown series (I’d go with “Here Comes The Pain”, since it should be only $20 at most) is not quite as good in a pure gameplay sense, but the Create mode makes up for that in a huge way. The degree of customization it offers is nothing short of astonishing. There’s something great about being able to create a replica of President Bush, then getting to kick him in the balls and bodyslam him through tables and so forth.
Rumble Roses is cheap, it has as good T&A as any game to date, and the basic gameplay mechanics are surprisingly solid given the poor trackrecord of T&A-centric games. However, it lacks the variety of match types that Def Jam and Smackdown offer, it’s roster is incredibly small, and there’s no Create mode to make up for that. The absurd story (very similar to the King Of Fighters games) almost makes up for some of this, but… no, actually it doesn’t. It’s really not worth more than a rental, or if the price drops a lot further.