Real-life R-type-stylish gfx material 10000x640 24bit picture, medium quality jpeg (adobe photoshop) -> 359k and still looking good. Jpeg is an impressing format, yep! (doesn't beat wavelet, though)
I have made a game that had 70 megabyte (!) sized levels (including parallax) in system memory and it ran smoothly. Walls were destructable of course.
The "visual artifacts" SiCrane talked about, mean probably the border of transparent and non-transparent on the jpeg level? Yes, that is a little problem, but I have solution:
Make a 2-color pcx (or png) that tells, where is transparent and where is not. And it being only 2-color pcx, it takes only few kilobytes of disk space.
And if you use more colors in that "attribute" picture, you can put there all the enemies starting places as different coloured pixels. So it's very easy to make levels also. You don't even need any kind of editor of your own to make levels!
If you planned to have only 100kb of tiles per theme, then there are not many of them (if they aren't hiqhly jpeg compressed..)!
So back to plain jpeg style:
500kb*20 levels=10 megabytes is not a 'huge' download these days if you get plenty of _good_ graphics in that size.
As I said before, many commercial games (CC,Baldur,Reap) don't use tiles anymore because jpeg graphics are just so much more beautiful.
--
And if you generate your levels, I still don't recommend tiles. Just make your generator draw the level in a huge bitmap, using clipart and stuff the way you like. I've programmed this type of level generator, too and it makes very nice looking levels.
