Hello W. Gilliland,
Sounds like you were a victim of some really crappy SEO sites / people in the past. A very hard lesson to learn no doubt.The one good thing is it has at least starting engaging you in the process. Nobody knows your business better than you, even the most experienced SEO in the world. Being able to speak some of the SEO language will not only help you communicate with them, but also provides the benefit of you knowing what the hell they are doing, or attempting to do.
Okay, onto the questions.
1. Am I still suffering from Penguin? To determine this you'll want to check your Google Webmasters and make sure you have no Manual penalty. Second, you need to evaluate every page's back link profile. The penguin algorithm doesn't apply to just top level pages but every page! Many many question and answer guru's have helped with other questions about this topic, perhaps thumbing through them to see if anything catches your eye.
2. Are you trapped in Panda and how do you know? First know what Panda was, it was an update that targeted low quality sites which were ranking well for keywords. Your site is far from low quality.. I don't think you have to worry about this directly, however in conjunction with the Penguin update which devalued crappy low quality links, it is possible that some of the "so-so" sites that were linking to you, may actually been hit themselves and warrant a link removal.
3. Do you need to remove more links. Possibly, your site is huge and it would take awhile to completely navigate your back-link profile. I enjoy helping, but this question is one that is not easily answered without research.
4. How can you start ranking for more keywords? Content is the key, and a huge obstacle for e-commerce sites. Maintaining tens of thousands of products can be extremely challenging. My advice is usually to focus on big keywords and pour on the content. For example, take a Brand & Category and write some compelling content for that page. I know Magneto is flexible enough to allow for custom pages, perhaps you can pick some of your best selling, or higher profit margin categories and dive in.
To continue on with this thought I will have to be a tad curt about somethings, but please don't take them offensively rather productively. What you have now is what I call a "Field of Dreams" website, that is to say build it and they will come. There is nothing wrong with this, if your goal is only to provide existing customers an avenue to shop from home. However, if the point of the website is bring in new customers and not just a service portal for existing customers then you have to do much more.
Example continued... I pointed out that you could focus on a Brand and Category, lets look at one (Paul Smith Footwear). To be honest I know nothing about Paul Smith, or their footwear, but that's okay for this example. Your page representing a keyword like "Paul Smith Footwear" looks like this.
Title="Footwear" (not okay)
Description="Default Description" (not okay)
Keywords="Magento, Varien, E-commerce" (not okay, tag shouldn't exist at all)
H1="Footwear" (not okay)
Content= nothing really, a search filter with product images
In this example I would recommend getting the SEO basics right, title, description, and populating some content. Because I know this can be a huge undertaking, you don't have to do your whole site at once, pick your top sellers or profit items and have a staff member or yourself write some content for the Brand and Product. Then use that text in conjunction with what you already have there.
Example Revised
Title="Paul Smith Men's Footwear, | Excel Clothing"
Description="Paul Smith men's footwear is handpicked fashionable footwear for all occasions"
Keywords=(this tag would be completely removed from all pages) H1="Paul Smith Men's Footwear"
Content = Use the keyword again, describe the Brand, and how the footwear makes you fell and look, how Excel clothing decides which Paul Smith footwear to stock and sell. Then show me the filter and product images.
In summary, you were hit by some bad SEO practices you'll need to be very proactive about monitoring all your back links. Continue evaluating each link and disavow the bad sites links. Ranking more keywords requires a complete look at the SEO basics and how they are implemented on your site. There is also room for improvement in the content department.
That is my take on the matters and I hope you consider them in the helpful spirit in which they were provided,
Don