Plight of the Concorde
88 Cities, 341 seconds runtime on NEOS

In a recent paper we constructed a family of hard to solve euclidean TSP instances. You can download the instances from this family as well as code for generating them here: 

http://www.or.uni-bonn.de/%7Ehougardy/HardTSPInstances.html 

The 88 city instance from this family takes Concorde on the NEOS server more than 5 minutes. The 178-city instance from this family takes already more than a day to solve.