For me personally, I'm looking at Europe. I'm coming from America so I could possibly get away with 3 month stints on a Schengen visa, but I've been looking for long-term 6-12 months.
I'm just starting to look into this though, so general tips/resources/strategies for getting the proper permits is always a plus.
As an aside, I'd never heard the term "Working Holiday" before so that in and of itself is a new avenue of approach.