The easiest way to add new software to your Mint installation is either via Synaptic Package Manager or mintInstall.
The first time you run mintInstall, it has to download lots of pictures and descriptions, so 15 to 30 minutes may not be unusual depending on your Internet connection. If you are really new to Linux, mintInstall will help you in your decision-making process since all the different application names and features might be confusing.
If you already know what you want, you can use Synaptic Package Manager to download and install what you want. Synaptic works fairly quickly, and I tend to use it regularly.
As you get more familiar with Linux, you may move on up to the command-line installations. Linux has all features available in different ways depending on your skill level.
It is my suggestion, that you being a recent convert, is to NOT go out on the Internet and try to download packages from other websites or sources. The Mint repositories have the packages that are specifically designed to work with your particular Mint install. If you stick with what Mint has, you will be much more successful.
Also, as an aside, when you update, please use mintUpdate with Level 1 and 2 packages enabled. You can use some or most of the Level 3 Ubuntu packages. Only you can make the decision as to what you need. The Level 4 and 5 packages really should not be attempted until you really have been working around with Mint and Linux for a while. Even though Mint uses Ubuntu packages, it is not Ubuntu.
You should have smooth sailing with Mint. Welcome, and have fun.
Edit: Chad and Viking type faster than I do.