The issue with defining the requirements is that there are so many variables to choose from. I suppose I can pick the base requirements, but even then I can't list immediately all the encoder settings I'd be using. At simple base level though:

Source: 1080i MPEG2 or 720P MPEG2
Destination: 720P h.264 23.97fps
Respectable rate: 2x+ real-time or faster using something like Handbrake's AppleTV 3 preset.

I don't want to spend $5000+, so by "cheap" I'm thinking maybe up to $1000.

Otherwise, I was thinking that the bare minimum would be a pair of quad or 8-core processors with large cache which is easier to spec blind with no budget.