Persian is a beautiful language when spoken.
easypersian.com was one of my main resources when I was getting started with Persian.
Persian for you is a radio course which offers basic phrases and vocabulary. Unfortunately, the links to many of the lessons seem to be broken. I have the mp3s in my hard disk, in case anybody is interested.
There is a Persian version of Deutsche Welle, which includes an audio section.
GLOSS, the Global Language Online Support System, makes a very good job at covering written and spoken Persian at all levels.
Persian in Texas is an excellent collection of resources.
Javid Jamae produced a frequency list of Persian.
If you read Russian, and even if you don't, you'll be interested in Ilya Frank's Persian texts. If you haven't heard of Nasreddin Hodja, I recommend downloading his stories. They are fun and lighthearted, yet wise and ingenious at the same time.
iranianlinguistics.org has compiled many resources at their wiki. Hopefully, you won't have to view the history to undo the spambot attacks.
Jon Dehdari has applied natural language processing to Persian. He has produced a dictionary and a frequency list, among other interesting resources.
On a completely random note, you can watch a short clip of Spongebob Squarepants in Persian at YouTube.
I started learning Persian the second day of 2010 using easypersian.com.
I bought a Persian dictionary from Iran which arrived to Chile three months after I ordered it.
Then I bought a phrasebook on October 2010, even though it was becoming obvious that I wouldn't be able to commit to Persian as needed in order to learn it to a good level.
I started Japanese after Persian, on November 2010.