Hi evb149,
I looked for what you're after not so long ago however without the need to run Linux. I looked at the Mico while using it in an Altera FPGA and a few others on openCores however found the process for all unattractive, I think the time you would need to spend in streamlining a good, fast development environment wouldn't be worth it. At least for me this is the case as I do actually want to achieve my end goal however much I do enjoy the process. In conclusion, because I like the Altera enviroment over Xilinx, I think I will buy a $500 license for the NIOS II. It does seem like the best option for processor speed, FPGA resources and development tools. The only thing really holding me back is the bad USD to GBP rate at the moment, $500 used to be £250, a long time ago now!
EDIT: Having just rang my local distributor I've learnt they do not deal with individuals (good job I run a business) and the license is just for one year. I'll have to think about this one and determine if I really need it. I do love playing with FPGAs and just about all projects I have in mind or currently undertaking could be made a lot easier and more interesting with a softcore.