5MBytes rbf for Stratix III is possible. You can check it on Altera Configuration Book (downloadable from the website). Also, the file size is fixed for a particular device, regardless of the design in it.
One thing I am a little confused. You said you target device would change to Cyclone III. Why do you still need a CPLD?
In terms of flash size, it depends on the target Cyclone III device you will use. Again you can check it on Altera Configuration Book. It lists the rbf data size for each Cyclone III device. (You can also consider using compression to reduce the file size.)