Has anyone notarized their birth certificate at their embassy? Would it be better to just get it there or any notary would do?

For what purpose do you need it notarized? For the interview? In Brazil we don't have to do that. We just show our original birth certificate (if it's a new one, better) and we're settled. Maybe if you give me more details, I can help you with my super searching skills.

Someone who brought their fiancee from Paraguay this year told me I would need it when it comes time to adjust the status here in the states.

Maybe it has to do with how they're obtained in Paraguay? Like, they could be copies obtained with a notary's office, perhaps - in Brazil they keep records of documents and issue "copies" of them. These copies are not really 'original' documents, but they're as good as one. We call them 'segunda via', meaning you asked for it be issued if the one you get when you're registered is missing or if you simply need one.

I read through some threads and FAQs and couldn't find anything about it.

First of all, let me start by saying that I don't even know what my birth certificate looks like. It's at a safety box in the bank. My mom said she had it legalized/notarized when we came to the US in 1993, but it has never ever been needed or has been used here in the states. I'm sure things have changed since 1993 though.
If your fiance doesn't need it for his interview, you can have it notarized at the paraguayan embassy here in the states. I highly reccomend that you get it done in Paraguay though. Besides DHL, my other annoyance is the Paraguayan embassy in DC. They're really hard to deal with. They hate being bothered, and take forever to get anything done (if they don't loose your papers that is).
If this is really becoming a big problem for your fiance, I can fiind out exactly what needs to be done and where to get it done. Hector is going to Paraguay next week, so he will definetly know.