What Altera Dev board should I get?

If a 100MHz cpu without floating point and with a small code/data memory will do what you need to do, the nios will work fine.

If your code/data is large enough to need external memory that will slow it down a lot more.

I'm not sure I'd actually want to run Linux on ot.

OTOH, if you don't use any of the Altera supplied library code (especially printf!), you only need about 4 asm instructions before jumping to C and you can do quite a lot in a small amount of code with no operating system code at all.