3 people you should talk to (besides city hall...any maybe an SBA counselor):
*Attorney
*Insurance Agent
*Accountant
find one you like and have them give you references for the others...you at least need to talk to an attorney and insurance agent.
An LLC has little or nothing to do with a business license. It is just a way to structure your business. The idea is with an LLC, the business is a "separate person" from you. So, if you drop a tree on somebody's house, they cannot come after your personal assets - because the LLC did it, not you. But that's where you need to talk to an attorney to make sure you don't do things that inadvertently unite the two. For example, if you make a mortgage payment out of the LLC's checking account, you have "pierced the corporate veil" and an now they can come after your personal assets...but if you also talked with your insurance agent, that should protect you as well!
Licensing and permitting is going to vary by state and city. It probably does make sense to do an LLC first (if you are going to) so the license is in the company name, not your name.
Besides an LLC, you can: be a sole proprietor, form a S-Corp, C-Corp. Partnership, or Limited Liability Parnership (LLP)...so, no, and LLC isn't required.
Oh...and don't forget to talk to IRS to get Tax Payer Identification Number (TIN). While this isn't necessary to start, it will be necessary if you pay employees. I'd recommend getting one as soon as you form the LLC...but see what your attorney and/or accountant thinks.