I work in a print shop for a living. We do stuff like that all of the time. For small runs, you’ll want it printed on a digital press. Otherwise the set up fees will be ridiculous. You’d have to print more than 1,000 calendars to make a traditional press worth it. And a good digital press will look almost as good as an offset (sometimes even better, depending on the press and paper). With that in mind, you might want to consider shrinking your calendar just a bit. A lot of digital presses can’t go that large. Usually, 12x18 or 13x19 is the largest sized sheet of paper you can easily get through one. Also, at the maximum size, they usually can’t print all of the way to the edge, so you’ll want a blank white border of around 1/8”-1/4” running around the edge of the paper, unless you go for a smaller size sheet (no bleed, as we say in the industry). Look for some local print shops and see what can quote you. Paper is heavy and expensive to ship. And here’s a dirty little secret of the print industry: There’s a good chance whomever you chose, they’ll farm it out to another local print shop. Printing equipment is very expensive to buy, expensive to maintain, and large. Each piece of equipment is usually specialized to do one thing well, so it’s rare to find a print shop capable of doing runs of 100,000, 1,000, and 100. Therefore, to keep your cost down, look for a small print shop that won’t have to farm it out. They’re more likely to specialize in small runs.
As for paper, if you’re going to have it done on a digital press, choose a glossy or matte/satin coated paper. For whatever reason, those presses don’t look very good with uncoated paper. It’ll be well worth the extra money.
And I’d avoid the super cheap places online like Vistaprint. They’re cheap, but their quality is terrible. We get a lot of business from people who went to Vistaprint or whatever first and then come to us to have it redone.