Hos
http://wopsa.se/ kostar det under 225 kr per månad att ha en så hög trafik som du har och servicen där är riktigt bra och hastigheten och uptime duger väl.
Angående dina ooptimerade bilder så borde du kunna fixa det serverside då du laddar upp bilderna till din butik, om du nu gör det via hemsidan. Även om du laddar upp bilderna via ftp borde du kunna köra ett script som skapar optimerade thumbnails åt dig automatiskt. Ett sådant script skulle inte kosta speciellt mycket om din sida är gjord i php iaf - har gjort betydligt svårare saker som inte kostat så enormt mycket.