Though if they were creating a new tileset, they would have to create a map to test it out as well right?
Haha, no. They'll make a test-map, I'm sure, to display the tiles. But they won't map for you for free.
I'm surprised the price is so high though. Is there really that much work in creating map tiles?
Obviously. It's work, and it takes a long time to complete a tileset, and time is money. It can easily lead up to $5000.
I wouldn't even give you a total price figure, I'd charge you per hour. I'm going to give you an example. I recently made a small tileset, interior and exterior, enough to make the inside of a house, a nature map, and a village. Not a lot.
Samples:
Just that was already over $1000. Took me about 60 hours.
Like if I hire someone to create a unique map without all the tilesets A1 to B and E. Just the ones that are required for the map.
This will be slightly less expensive (it takes a lot of time to work on making tiles seamless), depending on how many 'maps' you want the artist to create, and how many details it has.
Here is a map I created where the majority of the tiles were custom made for the map:
This STILL took me hours to do! And I'm a really fast worker. Not to mention the 'mapping' part still takes a lot of time.
Here is a map that took me 3 and a half hours to complete, WITH only ONE custom tile that I had to create for this map, the rest was already created.
Basically ...
if you want shiny pretty and unique tiles for your game, you need to spend a lot of money for them.
A better alternative is just hiring someone to 'edit' existing work for you, to make things more unique for your game.