Need new host-download WP myself/memory

It must be a common question: hosts. I am with one now (it was recommended but she doesn’t use WP) that not only uses an old version 2.0.4 (from 2006) but doesn’t provide enough memory for a decent plugin. I am looking for a new one.
Do I have this correct –
Some hosts provide WP for you to use with whatever version they recently updated?
Some hosts let you download whatever software you want to use.
And some use Fantastico to download WP. My current host doesn’t have Fan that I know of so I am not familiar with what it is. A downloading software?
Does anyone use AN Hosting? I read through many posts but cannot find anyone that recommends it. I like that they will kick back $$ to WP for further development.
Sabin-Wilson suggests Laughing Squid, AN & Dreamhost.
I had another person suggest not to use Fantastico but to download myself. Is something wrong with Fan?
Sorry so many basic questions but I want to get something started and have to start over. I guess then I’ll turn to a designer to help. Time limited to learn WP. The forums tell me just how much there is to learn and the room for error. Cheers and thanks!