Interested in getting started with an RPG, but there seem to be endless possibilities. What's a good base to get started with? What should I keep an eye out for at Gencon?


Look for any events that state "no experience required" or "all rules will be taught".
Many RPGs are good for beginners and have games geared for them. My preference is for D&D 5th Edition (5e), as it is really easy to get into. However, there are systems such as Fate, Pathfinder, Numenera, and more that are also pretty easy to learn.
What type of genre piques your interest most?
Here are some suggestions:
High fantasy - D&D, Pathfinder
Fantasy - 7th Sea, Legend of the 5 Rings
Sci-Fi - Star Trek, Star Wars,
Western - Deadlands, Western (not in English yet)
Espionage/spy - Top Secret
Detective - Baker Street
Horror - Call of Cthulhu, World of Darkness
Cross platform - FATE, Numenera, Shadowrun, Firefly/Serenity

Aaronmlopez provided you with a good list to select from. I would just add that if you can, try to get into a slot or demo the game before you invest in the rulebooks to first see if you like the game.
For most of these, you'll be able to find a vendor booth in the Exhibit Hall to get a feel for the system.
OH! Almost forgot...one more key factor to consider: While you'll likely see all of those mentioned played at Gen Con, you want to be sure you have (or can find) a group that will play those once you get home. A great RPG system with no players is just a book on your shelf. (I speak from experience)

I think this is the most important question that needs answering before any recommendations can be made.

What type of genre piques your interest most?
Here are some suggestions:
High fantasy - D&D, Pathfinder
Fantasy - 7th Sea, Legend of the 5 Rings
Sci-Fi - Star Trek, Star Wars,
Western - Deadlands, Western (not in English yet)
Espionage/spy - Top Secret
Detective - Baker Street
Horror - Call of Cthulhu, World of Darkness
Cross platform - FATE, Numenera, Shadowrun, Firefly/Serenity

Not necessarily. The basic concept of an RPG is playing a character (a little bit like improv acting around a table), but there are RPG adventures whose plots are less linear. That said, most convention game plots DO tend to be linear out of necessity (time constraints, etc.)
As far as fantasy RPGs, I'd recommend Pathfinder.

I do enjoy a good linear game.

Dungeon World for generic fantasy but faster battles when they happen
similar, yet d20-bound: Index Card RPG brought to you by the illustrius Hankerin Ferinale
Lady Blackbird for more concise, one-shot game
Fate is a bit more complex to GM, but is very good for stories.
If you really need to play D&D, Basic Fantasy is the same thing except free.
Other stuff to look into: Fudge, Gurps, Mouse Guard, L5R
I know there are systems/settings perfectly suited for mystery/detective/etc, but I don't know them.
If you're shopping around, you might want to look for the word "rules light".