I don't recall who or which podcast I heard this from but even professional comedians practise a lot. There was a metric of practising minimum an hour for every minute of your speech/act. It's not all about brute memorization, its the fine tuning of little things that make the delivery amazing.
Even the best still get butterflies. Public speaking is said to be very counterintuitive to our survival instincts since you expose a lot about yourself to a large group of people. Practise lets you manage that fear and fosters more confidence.
I think you'll learn a lot about speaking, and entertainment in general and will gain appreciation for good presentations.
Finally, you'll realize you won't reach out to everyone in your audience. In an average technical presentation, if 25% of my audience felt the content was too complicated, 25% too easy, but 50% just right, then I've succeeded.
Best of luck!
Various clubs (Toastmasters is the most widespread one) can provide that. But don't discount the benefit of preparing a speech and delivering it over and over again, even to no one. Filming yourself can provide the feedback component.
I think "Thank You For Arguing"  is a good resource on persuasion broadly. Some of the same things that work on a person-to-person level also apply to a speaker-to-audience relationship, and the book goes into both areas.
American Rhetoric has a library of audio recordings from "great speeches" . Listen, and imitate the things you like.
Finally, more than anything else, I'd actually recommend taking improv comedy/improv theater classes. They taught me two things: that not knowing what you're going to say next is totally fine, and that the audience is on your side and wants you to succeed. Knowing both of those things in your bones before you take the stage makes everything so much easier.
I have an interview style podcast and editing makes me very aware of verbal tics in both myself and others.
You may find it easier to record yourself while speaking to others though. At least for me, just talking into a camera in my office can feel very awkward.
ADDED: I have taken courses through my employer a couple of times. They've been useful but I agree with everyone else that observing others who you think do a good job, practice, and feedback are generally more useful than taking a course as such. I wouldn't dissuade someone from taking a course but don't go in expecting to learn the magic formula.
I've been a member for about a year now and it has made an enormous difference. I used to be absolutely terrified to public speaking. I would get so incredibly nervous and flustered that it would barely be able to get anything out and it would make everyone in the room super uncomfortable. But now I've become a halfway decent public speaker. And in translates well to all sort of other social interactions too. I'm definitely more confident overall.
It really is all about practice, and being able to do that in front of a group of people that are trying to do the same is comforting.
1. Actually speaking. For this, you just want to practice. Often times that's what you need. Toastmasters I've heard is great, but any chance you have to practice, just go for it. I'm a big fan of improv (I've taken the UCB course in New York while in college which is really fun!), as it gets to the principle issue: comfort. You just need to feel comfortable and part of that is really about learning how to harness your nerves. The difference in feeling between being nervous and excited may not be far apart from a physical perspective, so trying to channel those nerves and treat them as a Good Thing, is definitely what you want to do, and you're only going to get better with practice.
2. Speech writing. This is totally different, and is actually very different from something like essay writing. It's very top heavy, and this IMO can be picked up from just watching a lot of speeches. Alterations, keeping track of syllable count and sonic tricks help compose how your speech is heard, which is different from how it's understood. Learning how to get something to sound a certain way is something you don't think too much about when writing essays, but is paramount to writing speeches. In addition, learning how to format them content wise is also different from many other forms of writing. I find the best way to look at this (much like programming), is to look at existing speeches (like looking at projects), and try to understand what makes a speech 'good', and what doesn't. From Steve Jobs at Stanford to Barack Obama's Red States and Blue States (Obama really employs great melodic elements in his speeches in contrast to Jobs's more conversational story telling style) - there are many different ways to cut it, but the best is to look at what impacts you and attempt to deconstruct why.
Again, if you just want to be comfortable with speaking in public, just practice and throw yourself in there. The fear of having a bad speech is always 1000x worse than the reaction to having a bad speech. The stakes in public speaking aren't as high as most people think and often times the worst thing that can happen is boredom. I find the biggest mistake most people make is really thinking people care more than they actually do. So just go and try to have fun with it - and fake that confidence long enough until it starts to feel real :).
And different audiences, in different settings have very different expectations around things like technical depth and polish. Something could be a super-duper TED talk or keynote at a big conference and be utterly uninteresting for the audience at a local event that's there for technical deep-dives.
Feel free to email me if you need any suggestions!
Toastmasters will give you practice.
In would also recommend watching some great communicators. Like Martin Luther King Jr. I like his speech to Stanford called "the other america" (can't post link sorry)
how to thank a group when receiving an award. 1thank them. 2 tell them why and how the award means to you. 3tell them how you will use what you received. 4 thank them again.
This course is not cheap, but if you're serious, this was put together by a guy from a theatre background. If you think about it, actors have to learn to deal with all the things that speakers must deal with: anxiety, confidence, voice, body language, eye contact, presence, etc. This course was an eye-opener for me in many ways I had never thought of.
I highly recommend this after having been through:
Dale Carnegie - great orientation to people skills, but not a lot of speaking practice;
Toastmasters - "amateurs teaching amateurs" - groups vary widely;
Speaking Circles - touchy feely
They have clubs in most cities and sometimes multiple. I attended an English language club in Amsterdam and it helped me tremendously.
It's run by the members for the members and at least at the one I attended it was incredibly supportive and very affordable.
2) Related to "accents" : http://brunozzi.com/2013/09/02/accents-english-arrogance-suc...
If you're terrified of public speaking:
If you're a little bit more advanced:
I liked the book "Made to Stick" http://heathbrothers.com/books/made-to-stick/ about how to clearly present your message. They have a very good summary designed for presentations called "Making Presentations That Stick". The authors will give it in exchange of subscribing for their mailing list: http://heathbrothers.com/resources/overview/ (it is in the bottom of the page)
Courses and books give you tool. For sharpening, you have to use it daily.
Good resources about "tools":
> I'd Rather Die! Public Speaking Survival Skills by Robert Scanlon.
> MIT OWC - Rethoric 
> Oren Klaff - How To Pitch Anything (LondonReal) 
> (not exactly about speaking but suitable for speak preparation) Technical communication by Mike Markel 
> Leadership Presence
> Communicate to Influence: How to Inspire Your Audience to Action
1. Art of Argument - Giles St.Aubyn (ISBN 0800803698)
2. Influence - Robert Cialdini (006124189X)
After that, try reading some Bertrand Russell writings. See how your argument and persuasion quality jumps from above resources.
I attended her half day workshop in the Bay Area and it transformed my public speaking and made it easier fir me to build rapport with the audience.
when I record, I get to see my own body language, my phone changes my speaking voice and picks up my very strong Bronx accent.