Generating interesting combinatorial optimization problems
One general approach to generating harder instances is as follows:


Start with a random problem instance.
Embed a "hidden backdoor": randomly choose a good solution (one that's likely to be much better than any solution that already exists) and modify the problem instance to forcibly embed this solution into the problem instance.


For instance, for TSP, you could do something like the following.  Generate a random problem instance by picking a random $U(0,1)$ cost matrix.  Then, adjust the problem instance to hide a much-better solution in it: randomly select a tour that visits each vertex exactly once, and reduce the edge weights on that tour (e.g., generate it randomly from $U(0,c)$ where $c&lt;1$; reduce the existing weight; or modify the existing edge with some fixed probability).  This adjustment procedure ensures that the optimal solution will, with high probability, be that special tour that you selected.  If you're lucky and you select a reasonable embedding, it will also not be so easy to recognize where you hid the special solution.

This approach is derived from general ideas in cryptography, where we want to create trapdoor one-way problems: where the problem is hard to solve without knowledge of the secret trapdoor, but with knowledge of the secret trapdoor, the problem becomes very easy.  There have been many attempts to embed secret trapdoors into a variety of hard problems (while still preserving the hardness of the problem even after the trapdoor has been added), with mixed degrees of success.  But this general approach seems like it might workable, for your purposes.

The resulting problem instances might be hard, but will they be interesting, from any practical perspective?  I don't know.  Beats me.  They look fairly artificial to me, but what do I know?

If your primary goal is to select problem instances that are practically relevant and representative of real-world applications of TSP, my suggestion would be take a totally different approach.  Instead, start by surveying real-world applications of TSP, then looking for representative instances of those problems, and convert them to their corresponding TSP problem instance -- so you are working with problem instances derived from a real world problem.