If you have the space, I’d go with your idea of keeping all file sizes in constant units so the order of magnitude is indicated by the number of places consumed. With right-aligned numbers, that will make it easy enough to scan for a particular order of magnitude.
Keep in mind you gain about three places of space with this approach because you eliminate the units column, instead putting the units in the file size column header, so this won't be that much of a space hog. To save a little more space, consider showing sizes in MB resolved to 0.1 MB. For downloading duration with today’s broadband, once you account for server response time and variation, anything under 0.1 MB is going to seem to have about the same duration. It'll take no longer than loading a new web page, and users don't expect/need duration estimates for that. You can write it as “under 0.1” for files less than 50kB. Maybe even resolving to 1 MB is good enough if you really need the space.
A linear graphical representation of file size (e.g., a bar graph) is better for assessing relative download times. However, I can’t see it working well when your download durations span three or more orders of magnitude. Users will likely want to distinguish a 5 versus 10 minute download, so you need a visually noticeable difference of about 2 MB. I'd say you need at least 3 pixels for 2 MB for a bar graph, which pretty much rules out representing files of a GB or more.
You could try to linearly represent GB, MB, and kB with separate graphics, but such displays can be notoriously hard to read and harder to scan (e.g., multi-hand altimeters have been largely abandoned in aircraft because of reading errors). I wouldn’t try something like that unless your users get training or a lot of experience with it.
Trying to rank or categorize files sizes with icons, colors, font size, or number of symbols is problematic unless you know the proper breakpoints for your users. However, you probably can’t know because the threshold of acceptable duration is going to vary by the user, their equipment, and their situation (how much time they have). I wouldn’t use red for any file size unless you want some users thinking the file is so large that downloading might damage their computer or cause some other technical problem.
Codes good for ranking, like font size and number of symbols, may also be problematic because users might assume they are linearly related to time, when you’d probably need to use a logarithmic transform. Writing out the sizes in constant units doesn’t have this issue because it’s clear the number of places is logarithmically related to size, even for users who don't know what a logarithm is. If you want to try some sort of ranking symbol, I suggest representing size by the volume of 3-D solids (e.g., various sizes of cubes). This may help users understand that one step means a nonlinear increase in size. Of course, any graphic coding using more than one dimension can have row spacing issues in your table.
If you can’t use constant units, then graphically distinguishing the kB, MB, GB symbols is a good alternative. I’d consider using font weight for that. It’s somewhat scanable, but its real function is to increase the chance of users noticing the different units, not to help scan for files of a particular size range. This is fine if users are going to download the file anyway, but just want to be able to plan for the download time.
Actually, if the task really is about users finding files of a particular size range, sorting or filtering the list by file size (by default or as a user option) is probably the best solution.