Well, I'll take another tack on this, since I think you are talking about a companion piece to the grill itself?
1) Easy to clean surface on top. Sticky stuff will get spilled, so I'd think about the top being made out of something other than wood? Maybe granite, or concrete, or tile or something.
2) Big enough hold a 1/2 sheet pan. Heck, it might be nice to have a short shelf just under the top big enough to hold a couple of 1/2 sheet pans. I use these for staging and holding things prior to putting on and after taking things off.
3) Drawers. Be nice to have a relatively sealed area to store your bbq tools.
4) Other storage. Something to hold maybe a sealed bucket of charcoal, extra proprane tank, bbq cover, rotisserie, etc...
5) Durable. Must be made out of some kind of wood that will last and last out in the elements.
Sounds like a great project, keep us posted!
(Jay, you are going to get me in trouble, I want a big green egg, but my ole weber still works too good for me to justify getting another grill!)