I use NearlyFreeSpeech, and unfortunately, there’s no way to increase memory size, without paying three times as much for the site. And as it’s the same amount of memory I’ve been using with this site for the last few months, I don’t really see that being the problem. WP tends to fit in 32MB.
I’ve followed their directions to set up WP in the least stupid way with their architecture (install from SVN, set permissions on files in the right way, that sort of thing). And, I checked: they’ve not altered the amount of memory available, in the last few days.