I am currently living in Brazil and I am using the Michel Thomas course which I used to learn Spanish. It does help having a Brazilian girlfriend of course. There are quite a few differences in pronunciation between Portugal and Brazil Portuguese, the Michel Thomas method teaches Portugal but it is probably the best system around, especially for the price.
The hard pronunciation bits are the nasal sounds, but you get used to it. Also, the vowel sounds are kind of inbetween ours, but nothing really hard – its more a memory thing. It is harder to learn than Spanish as it is less regular and the sounds of letters change depending on position, but not so bad,