What is a good algorithm to generate a random path?

I need to generate a random path with 25 segments that never crosses itself between two locations in a 1000x1000 area. What is a good algorithm to do this?

My initial idea, which generates ok results, was to generate a random polygon using the space partitioning method and then remove one side.

The results look like this:

The downside of this method is that the start is always fairly close to the end (since they were originally connected by a line).

The other downside is since they were a polygon, the overall shape is generate some form or distorted circle. There are lots of types of paths that would never be generated, like a spiral.

Does anybody know an algorithm that could help me generate these paths?