As a fairly new pilot who does a fair amount of x-country flying I find myself "feeling" safer going East at 5500 and West at 6500 happily burning extra fuel to get up there. Listening to the on route frequency position reports as I fly, I find the vast majority of GA traffic fly between 3000 and 4500 giving me the feeling that things are pretty crowded and less safe down there. Is there any validity to this?
The altitude you fly at should be determined by the following:
Where you are safest. Crossing 5500 foot mountains at 6500 simply is not a good safe practice. Your altitude should be higher at night, if for nothing else, to give you more time to diagnose a problem or pick a suitable landing spot. When my primary students fly the hills around here, I insist that their final cruise be above 3000 AGL. That keeps them out of 2000 foot towers (most are just 1500 feet), and gives them time to pick a landing spot, and gives them altitude for getting radio assistance from FSS or ATC. Higher is better, but I tend to not encourage 10,000 foot level flights for student pilots because there are other risks. You should consider all the risks associated with altitude. Lumbering along at 11,000 feet may not be the least risk option.
Your altitude selection should help you in navigating. Being up higher lets you pick landmarks, see more VORs, reach more ATC and FSS facilities. Generally, my students do not use GPS (as student pilots), so if they get lost, they have to descend and read water towers and things like that to find themselves. That doesn't happen often.
Your altitude should keep you in good weather. If you are a VFR pilot, you will probably not want to make your trip on top, with a 1000 foot ceiling below you. Again one needs to balance risk. Being at an altitude which keeps you below the scattered layer, keeps visibility good, and can make a trip more enjoyable. But if Nervous Nancy is taking her first plane trip, and is predisposed to motion sickness or is simply nervous about bumps, then you want to pick an altitude that will be a bit smoother.
The whole exercise of picking the right altitude, the right route and even the right day is part of a big optimization problem, where you are looking at safety, enjoyment, economics and other factors. There is no magic altitude, no perfect route. What is good 80% of the time may be not so good 20% of the time, which is why ADM (Aeronautical Decision Making) is emphasized in training and recurrent training. Having good visibility, nice tailwinds, a smooth ride and plenty of altitude over the terrain are always nice.
Oh, one exercise you might try...I tend to do this with flight review students...we do airwork at altitude over the hills or low mountains about 25 to 30 miles from the airport. I pull power and they dive for the nearest pasture, which has down slopes which exceed the descent profile of the aircraft with power off, the gear and flaps down, and heavy slipping. Or select a field which has an up slope which is extreme enough so that a landing is impossible. Then I suggest that they try the home airport. "But it's 20 miles away." or maybe 25, and they might have a good tailwind at 5000 feet above the airport. And they start the glide. On the way we pick alternates, including flat grass strips, along the way. Almost 100% of the time, the lightly loaded aircraft makes the airport, and they are amazed that they were able to travel so far without power. And the take-aways are many, which include that having a couple of thousand feet below you really opens up your options. And to not pick the first field you see. With altitude, there may be others as you get to more favorable terrain.
I have managed to fly many decades, many hours and never so much as scratched paint on an airplane. However, before every flight and during every decision, I ask myself what an objective, after the fact, review board would say.
You have to get the concept that there is a "safe" cruising altitude above some level, because that idea bubbling along in the back of your mind will influence decisions, over such things as weather, which can work against you.
The most dangerous area in the VFR world is within a few miles of airports, because you have airplanes on converging tracks and descending, and the vast majority of VFR midairs happen close to an airport, with airplanes converging to the same landing circuit/pattern.
The chance of running into another plane just cruising along over the countryside, even if you aren't looking out for traffic, is microscopic.
That being said, when flying cross country, you go as high as is practical. The most air miles per gallon is found at the highest altitude you can maintain cruise power, and this this generally around 8000+/- ft, the level you can get 75% power at wide open throttle if you don't have turbocharging.
"Practical" means that what is optimal depends on winds and trip length (leaving out terrain considerations here). A 12 minute cruise climb to 8 or 8500 feet for a 30 minute trip may not be worth it if you're going to start down again as soon as you get there. On an hour long plus trip, it is. Same with winds. If there are strong tail winds aloft, you may get maximum net MPG by going as high as possible and cruising at less than 75%. If there are strong head winds, it might be better to go low to maximize ground speed. For any particular set of conditions, there will be some sweet spot profile that gets you from A to B on the least fuel if you're an owner, or in the shortest time if you're a wet renter paying by Hobbs.
With computer software, it's easy to work out the ideal profile for a trip based on distance and winds aloft and a lot of the nav apps out there have "VNAV" features that do this for you.
Go where you feel safest, terrain will certainly play a role (and be aware of migratory bird habits too!), as well as clouds and your ability to follow landmarks. Amazing how tiny even a runway can look from 6000 feet, and hazy/humid conditions can make it much worse.
If you are flying VFR, with other traffic flying in the same direction, they should be easy to see, especially if you have more than one set of eyes out the window. Resource your passenger(s) and monitor local radio for traffic.
Chances are, if things "are pretty crowded" you may be flying into controlled airspace. Otherwise, that situation is not the time to save your light bulbs. Especially if flying out of the sun, light them up, and weave a bit if flying into the sun.
Your thoughts on changing altitude to avoid traffic are sound.