What's the chance that Megaminx catches up with 4x4? There are more faces, but there are 50 pieces to place for megaminx and 56 for 4x4. If you figure that centers have one possible orientation, edges have two, and corners have 3 you end up with the following piece-orientations:
2x2: 24
3x3: 60
4x4: 108
5x5: 156
6x6: 228
7x7: 300
Megaminx: 120
I used 4.9 seconds as the basis, and squared the ratio of the number of orientations, and came up with this quite reasonable-looking estimate (2x2 single is already beaten, so I'll say this is the limit for averages):
2x2: 0.78
3x3: 4.90 (will probably be beaten, but it's my basis)
4x4: 15.87
5x5: 33.12
6x6: 1:10.75
7x7: 2:02.50
Megaminx: 19.6