I am interested in getting into the 4x genre and I would like to know what I should start with.

I already tried out Alpha Centari but I having trouble getting into that.

I would prefer that the suggestions are ones on GoG, so I would like to know about the accessibility of games like Star Wars: Rebellion, Master of Magic, Master of Orion, Age of Wonders, etc.

Check here:

http://www.rockpapershotgun.com/2014/12/08/best-4x-games-2014-endless-legend/

Age of Wonders: Shadow Magic is a pretty easy start. Nice tutorials for learning, I know some 4x game barely have one. I was actually going to suggest Alpha Centauri, I don't know, there's something about it that I just really like and I found it pretty easy to pick up. Now mind you, I'm no master at 4x and am still learning myself. I haven't played much Master of Magic, but I do have that one.

Well, for accessibility, you'd be hard pressed to beat Master of Magic or Master of Orion 2 (they're very similar, so if you've a preference to fantasy or space themes, that should be your discriminant). Setting up DOSBox is a cinch, so playing them shouldn't be a hassle. The only real problem I'd anticipate is if you can't handle the old, dated graphics. I's suggest you pick up one of those two, and also Age of Wonders 2 (possibly AoW: Shadow Magic as well). Those are probably some of the best classics of the genre.

Depending on what it is about 4x games that you like, you may also consider strategy games like Heroes of Might and Magic 3, Disciples 2, and Eador - but those reduce the city-management and empire-building in favor of character building and combat, so if what you really want is Galactic Civilizations (and who could blame you?), then these last three are not really the games for you.

Plus, they've all got fairly enthusiastic communities so if you do have any sort of trouble, post in the specific forums and you'll quickly get help.

EDIT: Added links, like I should have from the start

Noob question: When you say "hard pressed to beat" are you saying that they are hard to finish or that there's not much else more accessible than them.

If its the latter, then I think I will try Master of Magic as the visuals and music seem rather appealing too me.

The latter I would assume. Personally I never got into MoM. MoO is fantastic if you like space games.

Master of Magic and Masters of Orion 2 are probably the best to start with (aside from being genuine classics).

Great gameplay and genuinely have that "one more turn" factor - though ultimately, I'd say MoO2 is more the 4x than MoM (the latter feeling quite lightweight on the 4x scale - though no less a good game for it).

I'd go with OneFiercePuppy's advice - sadly, this is one occasion when I dont have a spare code for either game to shove in your inbox and force you to take the advice. :(

I'll go ahead and recommend Deadlock.

Thank you all for the advice I will check out MoM and MoO at some point.

i tend to take about a day with moo2, never finished a game of MoM myself - though thats also due to day to day circumstances.

actually, on the note of MoO2 - do you know if it works via play by email? - been itching to try some 4x games that way (dont like multiplayer usually, and my net is crap, but PBEM seems about right for me). still not got into tht - or fragile allegiance - another "whim" buy.
can you recommend an idiots guide to boost me into it?

You'd have to set all the combats to automatic, which would be a shame. It would be easy to send the save files back and forth; they're clearly named. But wouldn't a pbem game of MoO2 take you *months*?

sad but true: On a whim, I once played a "play by snail mail" game of checkers. It cost me over fifteen dollars in stamps XD

heheheh!
I suppose you would - but I've never bothered with the combat much myself - tend to let it run auto and issue major orders as needed.
hadnt though of it really.
ah well - back to finding someone to PBEM Civ 4 with then! ;)

If Alpha Centauri's a bit too complicated you might want to start with Civilization 2 but it's not on Gog.

Master of Orion 1 and 2 are classics and it's relatively simple to learn the basics on lower difficulties. Just stay away from Master of Orion 3.

Sid Meier's Colonization is fairly uncomplicated but it might look and feel a little dated.

I've played a little Deadlock, and while I'm not overly familiar with it I don't remember it being too bad.

In general the games published by Paradox Interactive are a bit complicated, but you might want to try Warlock: Master of the Arcane. It plays like a cross between Civilization 5 and Master of Magic. It's not on Gog though.

You might also want to take a look at Galactic Civilizations, it has a lot in common with MoO.