There are multiple maze generation algorithms. The one you describe the basic DFS algorithm. I'm aware of two other maze algorithms, both of which produce a lot more branching: Prim's algorithm and Kruskal's algorithm. Both of these algorithms are actually algorithms to find the minimum spanning tree of an undirected weighted graph.
Suppose you have a grid of points, which are connected horizontally and vertically to their direct neighbours. Then, assign each edge a random weight, and run Prim's algorithm to find the minimum spanning tree of this grid. Ta-dah, you have a randomly generated maze.
Now, the problem with mazes like this, from testing and experience, is that they branch a little too much. Most of the branches are one-square to three-square ordeals, and it's really easy to determine which branches lead to dead ends most of the time. You want somebody to be able to follow the maze for a little while before reaching dead ends.
So what you can do is to tweak the algorithm a little bit. One of the easiest alternate algorithms you can make is a "bounded DFS", in which you only go a certain distance inward on your search for a path before forcing a backtrack and branching again. This will create mazes with nice long stray paths most of the time.
As for modifying Prim and Kruskal, I don't know enough about graph theory to ascertain whether this method will actually work, but consider making it so that when generating the random graph at the start, the weights of edges touching the same point have to be within a certain distance of each other.
You can read more about maze generation algorithms on Wikipedia.