how much do machine shops typically cost?

If your going to put money into a block, go find yourself a late 80s/early 90s LA roller block. You'll be miles ahead of the game that way.
It depends on what your having them do. That said you'll usually pay more for a well known shop with a good rep.