A good workbench is without a doubt the most important tool in any woodworker's shop. A poorly designed bench will provide endless hours of frustration (as the OP expressed in his post) while a good design is more useful than a third hand or an apprentice. There are so many bench designs to choose from, and the debate will go on forever as to which one is "best". The two design styles that have the most longevity are the Roubo-style, and the classic European cabinetmaker's bench. That's the style Frank Klaus (and many others) advocate. It's the style I have worked on for over thirty years, and it's hard to find fault with the design. Tage Frid's third book (Furnituremaking) has a detailed set of plans for this style bench included as one of the projects. Building a bench like this is educational, it's rewarding, and at the end you'll have an essential tool for your shop.

My advice: get a set of plans for whatever style you choose, and get one built for your shop.