I've moved the thread to the database design forum for you (moving it requires Moderation privileges). I suspect that's the best place for this kind of question, although that's certainly subject to debate.
Excel is a great spreadsheet, but it is a pretty poor database. Excel can do trivial database manipulation, but any material degree of database complexity will baffle it (as you've discovered).
Almost any of the database products will do what you've described so far. The problem is that you're trying to eat a decent sized meal in one mouthfull... A messy proposition!
Break your problem down into smaller parts to make it easier to handle. That will make it much easier for you to learn too.
I'd recommend that you take about an hour to read up on the process of Database Normalization. You don't need to be an expert, but understanding the basics will help make this process a lot simpler. I strongly recommend Marc Rettig's Normalization Poster
for a great, quick overview of the concepts.
For what you've described so far I think you need three tables. Those are: Companies, People, and Tenures. Companies and people seem pretty self-evident to me. Tenures are a bit more complex, but they describe the relationship between a person and a company and would include details like the position the person held and the dates that the relationship started and ended. You'll often find that people will transition from one position to another within a company or even between companies, and will sometimes hold more than one position at a time.