Altera provides two softcores: NIOS II and ARM Cortex-M1. Both have Avalon interfaces and are available in Qsys.
NIOS II is probably more efficent than M1. More people have experience with it as well. ARM's advantage is if you're somehow planning to move on to a hard ARM processor.
Speakng of which, soft processors are *slow*. Mostly, they're used as control with any intensive number crunching being off-loaded to custom components.
If you need good CPU performance, consider one of the Altera SoC with hard Cortex-A9 processors.
Both are able to run Linux, but I don't know the state of the design tools for ARM.
Linux is portable and open source drivers usually work on all architectures.
Make sure you also check the licensing for the components too.
I suggest you get the tools first and tinker with them to get a better notion.
The web edition can't target a Stratix IV, but you can target a smaller FPGA instead.
You can also get a 60-day evaluation version, I think.