1. If you want to install Linux, no need to re-format first, Linux does that as part of the install.
2. obviously you need to download some Linux BEFORE overwriting your disk (unless you have access to another machine). I recommend getting a DVD iso download and ensure you burn it as 'iso', not as 'file'.
Note that many distros offer a LiveCD option, whereby you can take it for a test run, running purely from the CD/DVD, so no need to install at this point.
3. see www.distrowatch.com
for list of distros
4. what do you intend to use this for, as the choice of distro (Linux distribution) may depend on this
5. identity theft: can you clarify your concerns here; its not clear (ie this is not a common qn from someone in this position)
Linux is pretty secure, but that doesn't absolve you from being careful.
We can also give plenty of advice in this area, but it would be dependent on what you are doing eg web-surfing vs running a web server.
Here's a couple of good articles to get you started