By "squary like", you mean the video resolution is different, correct? Some video editors will allow you to crop and resize and combine different resolutions, I'm pretty sure premiere should have the toolset to allow you to do that.
Best quality is full frames uncompressed yes. Best Option? No. It's the equivalent as saving each frame as a .bmp file and then sharing the entire folder with someone. File size way too high.
The most popular options are divx, xvid, H.264, etc (mpeg-4 based codecs are most popular now, it seems). Don't bother using the older codecs. Render all your frames out as BMP instead of AVI to a single folder, put them together in a video editing application, and then compress it with a modern and popular codec.
Something you can read up on:
http://www.webopedia.com/quick_ref/Video_Codecs.asp