Apple's app store requires a 512x512 so you may be better off starting big and tweaking where needed as you shrink it (less so for simple vector-y stuff).
1. Short of checking out every icon out there, there's not a whole lot you can do to ensure this. Also, I'm not sure how common it is for people to just sue hard over an icon without at least sending a letter of varying politeness.
2. Keep it simple. An artistic squiggle in a circle. Some coloured dots. A couple of wavy lines. Or chuck a few coins to a designer friend to do you something simple.
Toolwise, I use Photoshop, though any half-decent graphics app can do it.
Don't add the rounded corners or shine for Apple submission though - they do that for you (or you can deactivate). Some templates are pre-rounded and come out a little weird.