Upload size limit

I am sure this is asked all the time, and I have read about it in a bunch of different threads, but still have no solution. I would like to be able to workaround the issue, as I guess my host is trying to squeeze me for more money.

I am using nextgen gallery, and it recommends:

Note : Based on your server memory limit you should not upload larger images then 2272 x 1704 pixel

and, it won’t let me upload anything of larger dimensions than that. (even though the actual file size might be less than 1 mb)

I also get this for each image

ID 121: A failure occurred
[more]
dsc_2941_3.jpg (Error : Exceed Memory limit. Require : 79.21 MByte)

Is it possible to get around this, or must I resize all before uploading?