What are their ages, and more importantly their musical tastes? Rock Band and Guitar Hero have quite a bit of diversity in the available songs, many different genres. Plus lots of downloadable content. I believe Singstar comes in a few different incarnations: 80's, Disney, etc.
Keep in mind that if you go the Rock Band or GH: World Tour route, you'll have a lot of plastic instruments to stow away when not playing. Also, don't be so certain that you yourself would never play these games -- there's bound to be some music in these games that you'll find yourself drawn to. 🙂
My personal preference is Rock Band all the way. I consider myself a hardcore music/rhythm gamer, and the Rock Band series gets nearly everything right. Many of the Harmonix staff (the company that developed RB) are musicians, and it shows in the game, it's very polished.