This is an interesting topic. I agree with your Grand Canyon as a border idea, and I've used it before myself. I suspect that the reason it wasn't used was because the straight line was set as the southern border of Utah Territory in 1850, while Powell didn't explore the Grand Canyon until 1869. Since that first date is pre-Civil War, I'm assuming there were some North-South politics involved in that line as well.
Although I have nothing to back this up, I believe there are a number of reasons for all the straight borders in the Western North America.
1) They allow you to write laws and treaties in fewer words.
2) At least the Rockies, due to the landscape, are extremely difficult to survey for rivers and watershed boundaries, and many of these lines were unknown at the time the border was created.
3) They are the product of an age where the culture believed that people should control nature, not vice versa.
4) Straight line borders don't move, like natural borders do (i.e. rivers change course, watersheds shift, meridians don't move)
5) In a lot of cases (the Grand Canyon excepted) there are a lack of good "natural" borders going through close enough to the right places to get what they're looking for. The Missouri would make a great northern border of the U.S., except that it bends back south at just the wrong places, you still need straight line borders connecting it to other things and to make sure the U.S. still gets most of the Louisiana Territory it believes it owns. It gets really complex when you start saying "Up the Missouri to the St. James, then north at it's northernmost point to the Assiniboine, then following that to the 100th parallel, then south to..."
6) Since most of these areas are relatively remote anyway, you can specify a straight line border and not have to worry about someone surveying it until ten or twenty years in the future when someone decides to sell the land.
I don't know which of these were prominent reasons, but something up there (or maybe something I didn't mention) must have been really, really good reason, because my last reason is more of an anti-reason:
7) Long straight line borders are more difficult to survey until technology has developed to late 19th century levels. In other words, there might be more longer straight line borders in the east as well if they had the technology to do so at the time. (As an example of where the technology was failing, look up the Walker Line. Of course, the resolution to that problem also led to the Kentucky Bend, which is another interesting border story).
There was also the issue that the U.S. had made some mistakes previously, and they probably wanted to avoid making them again by not relying on poorly or un-surveyed landmarks. For example, in the original border definition between the U.S. and Britain, they used a map that failed in the Western Great Lakes. This led to a border disputes when they found out the Mississippi stopped well south of the Lake of the Woods, and these disputes weren't resolved until the 1840's (at the same time they resolved the Maine border, which was also the result of the same map, but also a lot of miscommunication).