My #1 recommendation is plenty of table space for players to play on.
My favorite game store hosts a different group every night: Mondays are family-friendly board games, Tuesdays are Pathfinder, Wednesdays are D&D 4e, Thursdays are Dresden Files RPG, Fridays are varied (Shadowrun, Cthulu, etc.) and Saturdays are for Magic the Gathering. I think it is good to appeal to a variety of people.
Nice for D&D:
dice, dice bags, books, tokens, miniatures, tiles, mats (super handy)
Nice for a store:
They host a class every Saturday on how to paint miniatures and give a discount on paint. They have a printer and will print off a character sheet for you, or other small things you might need. DM’s get a free drink each gaming session
They have plenty of food available: sandwiches, soft drinks (including rare items like bundaberg ginger beer), sports drinks, chips, pretzels, etc. (cheese balls would drive me crazy and I’d go somewhere else)