You may be better off serving images off Amazon S3.
As to hosting providers, I have 4 years good experience with openhosting.com -- they provide virtual servers with root access etc, pay-as-you scale (starting $20 a month, then growing as your RAM /CPU/Disk/bandwidth grows). Another plus is that they sit on a very thick pipe.