There are a couple of apps that already do the hitting the note visual representation thing like Vocaloid for example and I've found it very useful. Unfortunately for them, though, they've got very very few songs to practice with and no way to add more songs which is why i gave up those apps it would be cool if you could improve on that.
Maybe also have a selection of separate songs that are for harmonizing. It would be different because you need to hire singers for those ones for example the singer demonstrates a aaA AA!! or something and then you try by yourself hitting the notes and then when you succeed you try hitting the notes again but this time you can hear the singer singing different notes in the background but you have to still sing the same notes over them.