If you want the fastest clock frequency and don't have high performance requirements, use the Nios II/e core since it is able
to achieve over 180 MHz in Altera's fastest Stratix I devices (e.g. Stratix I, 1S40, C5 part).
Even though you are using Cyclone and maybe a slower speed grade, this should give you enough headroom in Fmax.
BTW, on the fastest Stratix I device, Nios II/f (highest performance) and Nios II/s (medium performance) can achieve up to 148 MHz for a small system with small caches. The hard limit on Stratix I devices is the hardware multiplier which runs up
to 148 MHz. On fast Cyclone I devices, 125 MHz is about the fastest you'll see.
The fastest Nios I achieves about 125 MHz on the fastest Stratix I devices so using Nios II will help you achieve Fmax goals.
To get these frequencies, make sure you are using a recent version of Quartus, optimize for speed (instead of area),
and turn on all the physical synthesis options.