Skull Cove was my first set, and I found it plenty easy (and quick) to build a few cliffs.

I second Skull Cove - there are a good mix of builds in it - from very simple to moderately complex. I have gotten some very good use out of this set.

Castle Works Ultimate is nowhere near as challenging as it may appear - the variety in the set makes it look more complex than it is. And it will make a very impressive first build. You can even make structures that you can add on to over time. The biggest World Works build I have ever seen was made in that fashion - and was over six feet wide. (A friend of mine built Gormenghast as part of a gift for his brother. No interiors, but the thing was huge!)

The Auld Grump

Caveworks is easy and multi genre!

I would recommend Gothic Realms best in combination with missing persons for starters. The dark mystical rooms are straight forward to build. Together with the sewers they make for great fantasy settings. Plus you also get a great adventure along with it.

And while the maiden looks complex it really is rather easy to build. Denny included the best ever instructions and the build is very well ordered so you can't really go astray
So if you like a ship this is for you! (check out Noshrok Grimskulls build in the User Images Section of this board)

But of course a ship needs a harbor and places to sail to so Himmelveil (this also has nice interior props) and Skull Cove could be next

If you are looking for more versatility and something that can be used in almost every genre then Cave Works and Dungeon Works are nice too, me thinks

Sorry, but I find Village works a bit boring unless you add interior which makes it rather complicated for a beginner.
Interior Works on the other hand can be useful if you don't intend to build whole settings but like to put a prop or two on the table to give the general idea of a setting or to make it easier to play out fights indoors ...

In the end it all comes down to your preferences! Cause all WWG sets are great!

I really recommend to read through the short intro of each set. It has a detailed list of all parts included.
Also don't fail to get the free standees while you order. There are some great monsters and people in the free sets! You'll find those in the Kitbash section under "Official Freebies/Bonus Material - the lowest button on the page ...

and while you are at it, don't forget to post images of what you are building for everyone to enjoy

I started with Bits of Mayhem.

I think this is a good starting point because you'll get some very usefull props for scifi or modern games even if you'll decide not to build whole sceneries.

And this set will put your abilities to the first test with it's fiddlier parts.

I started building some sceneries for a campaign of SW Necropolis but quickly came to the decision that building a whole set for each and every session of game play was far beyond my time limits.

So nowadays I'm playing on a battle mat but the props from Bits of Mayhem are still in use.

I agree that the Maiden is a fantastic build. I'm kind of a beginner myself, having only ever built small props before, so the Maiden is my first actual large build.
And I'm amazed how easy it is to build, too. The instructions are very good and the model comes together very well. I don't want to brag here, but as Echizen suggested, take a look to see my actual build (and if you look at the dates I posted the various updates, you'll also see just how fast this comes together...).

I'll throw in my hat into the "Maiden First" ring. I started with WWG for the Maiden (I'm running a strongly pirate-themed campaign, and it has come in very handy) and it was very easy (although lengthy) to build.

If you've already done some basic work (the Wormhole stuff that's available), and can use the Maiden, it's well worth the build.

The Maiden is worth it even if you don't have a use for it.

I'm not sure if my Maiden will hit the game table (as none of my games involve pirates or any kind of ship action), but I think I will find an excuse to make that happen anyway...