What is the proper procedure to change altitude when changing heading?
TL;DR:


  Do you change altitude after the heading change, before, or during? 


When flying under Air Traffic Control, you are expected to execute instructions after you receive them, following the motto Aviate, Navigate, Communicate. When receiving a turn and climb instruction at the same time, you are expected to start both, e.g.

 DELME, turn left heading 220, descend FL80



  What's the proper procedure for changing altitude when you change headings? 


You do not change altitude or flight level on your own when flying IFR. When flying VFR, you should adhere to the semi-circular rules when changing your direction and end up in one of the semi-circular areas. On turn techniques that allow direction change and altitude change at the same time, see Tyler's answer.


  Is this made more complicated if you are flying Visual Flight Rules instead of Instrument Flight Rules?


Yes and No, because remember: You do not change altitude or flight level without being cleared or instructed to do so when flying IFR. Whether having to choose the correct altitude or flight level when flying VFR is more difficult than having ATC select one for you, is debatable.



Additional Information:

The rule you are talking about is the semi-circular flight level rules, which depending on the country, can either be applied West to East or North to South. Let's assume the example you have already used and differentiate between westbound and eastbound flights.

(Image Source: TU Wien)

The above picture shows that aircraft on a eastbound general track between 000° and 179° are bound to odd flight levels, such as FL210, FL230, FL250, etc.

Opposite traffic on a general track between 180° and 359° is bound to even flightlevels, such as FL220, FL240, FL260, etc.

This flight level you are bound to use is also the flight level you request in your flightplan, called the Requested Flight Level or RFL.

Imagine you have a flight going westbound and you have requested FL280 as your cruise level. You would maintain this flight level until you are cleared to descend by ATC. Even if a portion of the descent or arrival route leads in the opposite direction of your orignal track, it will be ATC who is responsible to assign the correct desend flight level, but these do not have to be necessarily following the semi-ciruclar flight level rules.

There is one scenarion where a pilot may want to initiate a flight level change due to changing jurisdiction and use of the semi-circular flight level rules, which is when crossing borders between countries that use west-east and north-south rules. If are on a westbound flight (approx track: 200° that requires even flightlevels, such as FL280 and cross the FIR border into a country with north-south rules that require an odd flight level, you would have a step climb or descent in your flightplan to accomodate this, e.g.:

[...] FIXXA UZ123 CROSS/N0265F290 UZ123 FIXXB [...]


It would still be ATC who clears you to climb to FL290 at that fix, but this way your flightplan is in accordance to local semi-circular flight level rules. Remember that when flying IFR, you never change the altitude or flightlevel unless you have been instructed or cleared to do so.

The same semi-circular flight level rules apply to VFR, just with the added 500ft to stay clear of the IFR flight levels. In most cases however, VFR does not entirely follow these rules, as the are VFR and their separation is based on visual identification and the see-and-avoid principle.

I am not familiar with airspace class B procedures, but in class C airspace, you require permissions to enter the airspace and will thus be assigned restrictions, which can be either a single altitude or flight level, an upper or lower restriction or a level or altitude band. If you are assigned either of the two latter options, you could apply the semi-circular flight level rules.

See below on an overview how other countries handle these semi-circular rules.

(Image Source: Delta Virtual Airlines - Not for real navigational use)

See also these related questions:
What is the difference between “flight level” and “altitude”?
What differences are there in Flight Level rules, internationally?