This is an excellent question (IMO). I've worked on a number of different projects like this. I think for things like a pergola, cedar would be a great choice. It is relatively light, is easily worked and weathers beautifully.
Pressure treated is great when it won't be visible. I find it does not stain or seal exceptionally well, however it is strong and dependable. Think stringers and joists.
If you're willing to spend a little more, one of the most weather resistant AND strong woods I've worked with is Mahogany. It is available in a number of different forms. I've even use an engineered 4x4 post that was made up of no less than 15 pieces/strips laminated together. They were pin straight, and unless viewed from a cut end, you would not know they were not solid mahogany (which would have been ridiculously expensive.
There are also a number of great systems that are effectively cases that surround another structure. Think looks of 4x4 timber, without the weight and possible bowing and twisting.