The final goal is to create a road system similar to the one in Diablo2. A random enterance and exit are plotted on the map, then a winding path connects the two nodes. I have implemented a system that selects two random places on the edge of a map, then connects them. My issue is that the path is rather boring. Are there any good ways to improve the path my road takes? This is what I currently use to create the path:

        private List<Vector2> generatePath(Vector2 p1, Vector2 p2)
        {
            List<Vector2> nodes = new List<Vector2>();
            nodes.Add(p1);
            while (!p1.Equals(p2))
            {
                float xDiff = p2.X - p1.X;
                float yDiff = p2.Y - p1.Y;
                double atan = Math.Atan2(yDiff, xDiff);
                double quadrant = Math.Round(4 * atan / (2 * Math.PI) + 4) % 4;

                if (quadrant == 0) p1.X++;
                if (quadrant == 1) p1.Y++;
                if (quadrant == 2) p1.X--;
                if (quadrant == 3) p1.Y--;

                nodes.Add(p1);
            }

            nodes.Add(p2);

            return nodes;
        }

I've done something like this once, but used A* with weights in map according to different terrain types/features (rocks, dense wood etc). This way the road follows nicely the landscape, walking around large rocks or lakes, for example. It's good to make rivers, also, just use the height of the terrain cell instead of the "difficulty" to pass.

Another way (but never implemented) could be using waypoints. Put some random points between the start and the end and force the road to pass through them. You could add later features on these points, like inns, fountains, towns, or something else to justify a nearby road.

I've been avoiding a* since I'm not really sure how to implement it. I planning on generating the road first and then the landscape around it, does it really matter what order I do this in?

I like the idea of using waypoints, I may attempt something like that. I was looking in to midpoint displacement algorithms which would make the road look more natural, the issue is that it still takes the shortest path.