Nice looking rice everybody!
I make paella all the time on my Performer in the summer. A couple of things I'd suggest:
1. Get a real paella pan. They're dirt cheap, and they really take the rice to a new level. The edges get crispy while the inside stays moist but separate. I use mine for stuffing too for that same reason. Season it like cast iron and you're off.
2. Smoke the sucker! Real paella in Spain is cooked over orange trimmings, and those suckers smolder when they get cooler. I always throw a chunk of fruit wood into the coals when I close the lid to let it finish baking. The extra blast of smoke is wonderful.
3. Look up Jos? Andrés' recipe for salsa salmorra. It's a smoker, spicier, garlic paella base. I make about 2 cups at a time and freeze them in single serving sizes. That way, I'm ready to go with paella at a moment's notice without much trouble. Add meat, rice, veggies, and smoke, and you've got a weeknight party.
Stan
...and good Spanish wine or American beer, of course...