The Traveling Salesman Problem is perhaps the most studied of all combinatorial optimization problems. There has been a lot work in solving TSP instances to provable optimality. Concorde solves very large instances to provable optimality, with the largest solved having 85,900 points. There is a 100,000 city problem that has not been solved to provable optimality. But there are some smaller instances not solved to optimality, with the smallest at 6732 cities. Is this the smallest "difficult instance"? Are there small TSPs that are hard for Concorde or other other optimization approaches to solve?
There is a paper of Ahammed and Moscato on finding hard instances for Concorde using Lindenmeyer systems. They were able to find small instances with about 1500 cities that took (in 2011) more than 4 hours to solve.
One should probably add that "hard" always means "hard for some algorithm". So, for balance, here is a paper of Kate Smith-Miles & van Hemert studying hardness for variants of the Kernighan-Lin algorithm.
For more on the pitfalls of "hard" versus "easy" in the context of SAT, there's an excellent talk of Moshe Vardi where he concludes that "the 'easy-hard-easy' picture is patently wrong".
There is a paper by Papadimitriou and Steiglitz here to construct instances, which are very hard for local searches to find optimal solution.
Hard to Solve Instances of the Euclidean Traveling Salesman Problem provides awhole class of hard to solve small instances for the planar Euclidean TSP; the are also downloadable instances.