Examine the files you have now for resolution, audio codec, framerate and bitrate. You can do this with MediaInfo or Gspot video utility. Use an encoder (there are dozens) where you can adjust these settings. In particular you may want to reduce resolution to something like 320 x 240 (4:3 aspect ratio) or 320 x 172. Reducing bitrate can also reduce the overall size of the video…though sometimes at a cost of quality as you have noted…depends on the codec used for the video though as some are more efficient at compression.
A common format is xvid or divx mp4 with mp3 audio. If you are uploading to Youtube, they will reprocess your videos over to flash format.
One tool with control over all these settings is Xvid4PSP. The name is misleading, as it can convert to many different formats. It will go to .flv (flash) format directly if you want. Xvid4PSP is free to download and use.