YouTube support a number of different options for uploading:
- WebM - VP8 for video, which really isn't that great
- MPEG4 (h264) - pretty much the standard
- AVI - a container format, not a codec
- MPEG2 (DivX, XviD) - higher filesizes for similar quality as compared to h264
- WMV - not used by many outside of Microsoft for good reason
- FLV - previously used to contain VP6, but currently uses h264
Really, for general-purpose video, everyone should be using h264.
The audio codec you choose is not going to make much a difference for a standard YouTube-length video, as long as it's lossy. I don't believe that YouTube accepts any lossless audio anyways, not to mention that it would be a ridiculous waste of disk space.
Realistically, if you want to produce really small encodes that don't take up much disk space, you'll have to spend many hours tweaking settings. I assume that your upload bandwidth is not capped enough to make this kind of effort worthwhile, but it would be nice to see what kind of change you're hoping for.
See also Google's help article on optimizing videos for upload.