+1 on the surly. My husband has a steamroller and loves it, and pretty much all their frames can take fat tires. And they're not terribly expensive new - the steamroller was $600 (but it's a fixie, I think the cross checks are a bit more but still under $1000). I would imagine you could get one used within your budget.