A software repository is built in with nearly all Linux distribution. Ubuntu, for example, goes a step further and offers a nice wrapper for their repository called the Ubuntu Software Center. Simply search for the task you're trying to accomplish with software and the provided repository front-end will give you a list of possible programs.
If you're still not finding what you need, the final thing to consider is using Google, but with this warning – be prepared to find compatible packaging to install said software. For example, let's say you needed the latest version of a specific video editor as the version on the repositories was too old for your taste. Ubuntu users might be able to find the latest version on the Web, only to then discover they are asked to either install the deb package or perhaps the Personal Package Archive (PPA) instead.
In both instances, there is a matter of trust here as you don't have any official way of knowing if that software is safe. Since a PPA is a personal archive, you're indicating that you trust the creator of that PPA and the contents of its packages. If you don't, stick to using official distribution specific repositories instead. Better to be safe than sorry.
While it's true that Linux on the desktop doesn't have any immediate malware threats that warrant great concern, it's critical to remember that anything that executes code has the potential for danger. Desktop Linux distributions simply aren't really big malware targets.
One aspect to this you should be aware of is that Windows malware can still affect Windows users. Because of this and the fact that this can be passed along by Linux users through shared network folders, etc, it's advisable to use a tool like ClamAV. Designed to scan for Windows malware on Linux systems, ClamAV should be used if you're concerned about potentially sharing malware with Windows systems.
In truth, the biggest threat to a Linux installation is going to be a hacked Web account or potentially doing something to lose local data on ones hard drive by executing random code. In short, the best things you can do to increase your system's personal security is to be aware of what we're accessing and how we're doing it.
At the end of the day, making the switch to Linux distributions such as Ubuntu comes down to one thing – commitment. If you need an operating system without being willing to learn along with it, then Linux isn't for you. If, however, you're willing to put on your thinking cap once in awhile, then beginner distros like Ubuntu could be a good match for you.
Lastly, when at all possible, considering buying PCs with Linux preinstalled. Google will yield you a ton of choices and you're assured that you won't run into any compatibility surprises. Be it rare, they do indeed exist and there are forums loaded with examples, usually with oddball chipsets or proprietary drivers for AMD cards.