File size is critical for users who have paid internet traffic, estimated download time is important for slow connections or large files, so it's a good idea to show both size and time.
I believe that many of users are aware of file sizes because of the smartphones, 3G, "cents for megabyte" etc. So personally I don't see any real problem with this.
Concerning implementation.
I can not find a link to the site I saw this, but you may think about something like showing size of the file and several different estimates depending on the connection speed (or type), like:
File size: 23Mb
Estimated download time: Less than a minute for broadband and 4G connections and Up to 5 minutes for 3G connections.
I think you should limit number of possible connection types to 2 or 3 (of most common connection types in a region, etc). The main idea of time estimation (and size) is to help your users decide whatever they may download file right now or should choose another possibility (depending on their situation) and download it later.
The drawback of guessing on how long it will take for the certain user and certain connection is that you may be wrong (inaccurate) because of different reasons, so, you may estimate download in 5 mins, but in reality it will take 15 mins (because of traffic which start to grow after the download has started, etc) and that's bad, because your user will expect it to end in 5 mins (and that was you who told him that time), so I think it's better to show some average estimates instead. Most of the download managers/web browsers has an estimation build in so users will be aware of download time anyway.