720p and 1080p are square pixel formats, so you should reduce their size in proportion. 1920 x 1080 could be reduced to something like 960 x 540 or 640 x 360. Same holds for the 1280 x 720 resolutions seen in your 720p files. Since HD is not a priority, I'd go for the 640 x 360 resolution when reencoding.
You should test playback with this resolution in your netbook first. Don't know how much help CoreAVC will be on a netbook...never been in a position to try it.
H264 in an mp4 or mkv file would give you smaller files, but takes more processing power to play correctly. AAC or AC3 audio would work. Try this in Handbrake with a constant quality encode set at 20. You can also set Handbrake to crop the black bars.
You could also try the xvid codec in an avi container, which would be easier to playback but would result in larger sized files. And Handbrake no longer does xvid or avi's, so you'd have to try a different encoder.