Ben,
When I was "hand-crafting" my badges (up until a week ago... thanks mate

) I used 256-colour PNG and reduced the badge to 75% of it's default size.
While I'd love to be able to get the new auto-badge smaller (far future suggestion...), of more use would be limiting the palette down from 24-bit (particularly on file sizes, and hence loading times).
Example: just threw my auto-badge ("Raw" 24-bit, 25.4KB) through PSPX and I come up with the following (Optimised octree, 256 colour, 8.89KB):

If you compare it with the "raw" file (my avatar) they aren't really all that different.