My site produces regular videos and they need to be of a decent size for downloaders (plus the fact that I have to upload on 56k) and must be in a format which the majority of regular people have.

Currently I use MPG's which convert about a minute's footage to 5MB, but the quality gets hit badly.

Can anyone recommend any better formats/softwares to use?

(I have Arcsoft VideoImpression 1.6, Movie Maker 2 and Ulead VideoStudio 5.0 to use however I can get nearly all softwares)