I mean, I love Myriad, I loved it way before Apple started using it. I named my cat Myriad. However, I’ve used it (in various weights) for 3 or the 4 recent logos I’ve done and I need something else! And I use it all the time in body copy too. It’s just so clean and nicely kerned and reads well at small sizes. But I’ve got to expand into something new for corp logos and brochure copy ASAP.
The Rotis family is nice IMHO, although quite widely used in the corporate world so may not be “different” enough for you.
But really, we only ever need one “fancy” font, right? 
Serif: Goudy Old Style
San serif: Helvetica
They’re both so pure, so clean, so elegant. It just doesn’t get any better.
Perpetua for me!
I like Copperplate, but I’ve just noticed Hobbyhorse. Are you talking about everyday plain typing? Times New Roman.
If you want sans serif, then I believe I have sung the praises of Gill Sans before. It looks good for the types of things the OP is doing - logos and brochures. I do love Myriad myself, though; I use it for setting tables in my books* because it looks so clean at 9pt.
For serifed fonts (book copy) I’ve been digging Warnock Pro and Minion Pro because they have matched Cyrillic and Greek character sets (though not accented Greek, boo). Also nice is Dante, if the subject matter is fairly contemporary. Yeah, I try to match my font to the historical period addressed in the content, I realize that makes me a huge geek. 
*Boy, that phrase looks goofy if you don’t know what the context is.
I was stuck in the Helvetica Neue family for a while. Lots of different weights, extendeds were nice too.
I like Hoefler Text and Garamond . I did a book in Hoefler Text last year, I like how it looks classic and a bit old-fashioned without being gimmicky, stale or “Ye Olde Tyme.” My wedding invites are going to be in Garamond.
For sans serif, another vote for Futura and one for Helvetica, too.
Some great suggestions: Rotis I haven’t used before, I like that it’s a little condensed. Goudy old style I used for a law firm, that’d be good to bring back. I have an irrational dislike of Helvetica (except the lights); that small apeture on the lowercase e makes it look like it has a headache. 
I also irrationally dislike copperplate fonts, unless I was maybe doing a restaurant logo. I am looking for plainer fonts–I work for conservative corps and web 2.0 companies, but not so web 2.0 that I want to do everything in VAG rounded. Perpetua, Futura and Gil Sans are great choices, I will add them to my shortlist. Minion I try to use, but I’d like the x-height a little higher…Warnock is a good one I haven’t used before.
Another vote for Garamond for a serif font; it’s what I use for my resume.
For sans serif, I’ll suggest Optima. One thing I find neat about Optima is the “cupping” of the ends that you only really see when it’s blown up to a large size. Take, say, the capital E. See how the terminal bit of every line is slightly concave? Nice.
Humanist is my favorite font. sigh I don’t get to use it very often. I spend most of my time recreating logos - it’s all Helvetica, Arial, and the occasional Futura. And Times New Roman. God, I hate TNR. Seriously folks - writing your name in all caps TNR does NOT count as a logo. (I mostly deal with hardware stores, kitchen supply, tile companies, things like that.)
I’ll second Gill Sans too. The lower-case g is just beautiful.
Or a very good designer!
I’m partial to old-fashioned fonts with lower x-heights; I like Gil Sans, Goudy and Garamond, Bodoni for something a little more modern and stylized, and (as somebody mentioned upthread) Futura for a very modern look. I’ve recently taken a shine to Optima, as it’s an elegant sans-serif font that has a strongly varied stroke weight. It comes across as more formal than most sans-serifs, but less formal and old-fashioned than most serifed fonts.
ETA: I second everything Silver Tyger Girl said!
Not useful for much at all, but I’ve got a liking for Karabine. Wish it had proper caps though, instead of back-to-front versions of the lower-case. 
Obligatory link to designer: Welcome jonathanpaquette.com - Justhost.com
I adore Papyrus. Not the most practical font in the world, but so elegant, so dignified, so fun and even, I dare say… epic.
Sorry, oliversmarch4th, but the Ruling Council of Graphic Designers has handed down a recent resolution that any use of Comic Sans or Papyrus, and any use of Trajan for movie posters, will be punished with the death penalty. 
I’ve mostly been using Palatino instead of Garamond, but maybe I’ll try it in my latest projects, I’m not 100% sold on Palatino where I’m using it. OPtima’s a good call, I like more humanist sanserifs.
Nooooooooo! Don’t use Papyrus. It’s the second-most overused font (after C0m1c @n).
Futura may be my favorite font, but it’s on its way to overexposure, seeing that Wes Anderson uses it for all his stuff. I like Georgia.
ETA: Gaudere beat me to it!
A law firm I worked for used to set their publications in comic sans. You are a LAW FIRM, don’t DO that! Plus lawyers like to use bold, underline, italic and ALL CAPS ALL AT ONCE.