I've never owned a projector, but what I would do is make sure you're connecting to it at its native res, which is 1280 x 720 I think. Then, instead of playing back some random downloaded standard def .avi, test it out with some 720p material that you know is good--rip a bluray, then use Handbrake to create a great quality 720p file. Then test with that.
And don't be afraid to use something other than VLC, around here very few of us use VLC as a main player--it's really a kitchen-sink, last resort player.
Depending on which MBP you have, your built-in display might be better than 720p, my really old Macbook is 1280 x 800, but generally, yes, the more you blow something up the higher res that file needs to be to begin with otherwise it will look worse than on a smaller display.