I actually picked up singstar for the PS3. The original game, the abba version, and the two mics (all used) cost me about $25 US. Lots of songs and it judges your pitch.. plus you can get instant feedback on how you sound.
As for what songs.. whatever you like. You can sing male or female roles in a female voice. Or switch back and forth and work on your range.