Hi Norsk,
Corks from the bark of the Cork Oak tree would be the corks that cause a wine to be corked. Synthetic corks are still being evaluated by many wineries for long term effects on bottle aging along with any "off-tastes" that they may produce.
For a starter wine I would suggest that you figure out what direction your tastes lie. That is, do you like something dry and heavy, sweet and fruity, spicey, plump and jammy or somewhere between those.
If you like your meads semi-sweet to sweet I'd suggest something like a Chenin Blanc, Gewurtztraminer, White Riesling, Grey Riesling or Johannesburg Riesling.
If you like your meads dry you might try a Chardonnay, Fume Blanc, Sauvignon Blanc, Dry Chenin Blanc or a White Bordeaux or Burgundy.
As far as reds go you really have to try them. I would suggest a good jammy Zinfandel with some lamb or beef, maybe pasta to begin with. By jammy I mean the wine tastes of black, plump and ripe fruit like plums, blackberries, currants, etc. It will have a distinct zing or spiciness to it (not a hot spiciness) that is unique to Zinfandel wines. There will be hints of vanilla, chocolate, and caramel, and there will be distinct dryness in the front of your mouth and in between your teeth and gums in the front of your mouth.
Cabernets are all over the map but can range from "suck the moisture out of your mouth dry" to pleasantly and velvety smooth. It must be said that this is true of many red wines.
For Reds, some names to look for are:
Zinfandel: Cosentino Vinyards - Cigar Zin, The Zin;
Tobin James Vinyards - Ballistic, James Gang; Elyse Vinyards - Morisoli, Howell Mountain; Zoom - Alexander Valley 86 Yr Old Vines, San Francisco Bay 108 Yr Old Vines; Rosenblum; Spelletich - Tim and Edie.
Cabernet: Henry's Drive 2002, Hanna Vinyards 2001, Claudius 2001 , Three Theives (in a one liter jug with a screw cap GREAT WINE GREAT VALUE), Five Vintners 2001, Marquis Phillips 2001, Bommarito 2001
Also take a look at Shiraz, Pino Noir and Merlot, these three tend not to be "big killer reds" like the Zinfandel and Cabernet do.
Oskaar