Within a debian/ubuntu distro simply:
apt-get install avidemux
Or For other linux distro's, Windows, MacOSX click here for Avidemux for your specific os
Open any video you want to encode for you G1 Via "Open"
Anyways Install Avidemux, then click on the video dropdown on the left and select MPEG-4 ASP (lavc)
Then Click Configure->Encoding Mode->Single Pass - Bitrate
Enter in any bitrate up to 384 to be safe, then click ok.
Now click Filters->MPlayer Resize->Double Click on it->
Click Ok, then close.
Ok I heard that mp3/lame worked but i tried and it failed with the "Video Player" app, so what works is this:
Click Audio->AAC (FAAC)
Now Click Format->MP4
Click Save and specify a name.mp4 for your video, then once its done encoding, plug in your G1 via USB and transfer the video to your G1, I made a folder called "Videos", the name doesn't matter.
Anyways I hope this works for you, I would suggest downloading a sample xvid video and experimenting, let me know how things go!