I've never used Nios II, but from the technical specs it looks quite impressive. I think you'd be hard pressed to find a C programmable core that is significantly better.
That said, the license can be an issue which is why I have my own (GPL'ed) solution: A MIPS compatible 32-bit core (
http://thorn.ws/yari). I'd love to see a performance comparison between it and Nios II, but I haven't yet taken the time to do it myself. It certainly won't satisfy the OP as it weighs in at ~ 7k LC, but performance was priority for YARI, not resource consumption.
Regards
Tommy