First off, as you mentioned, Ebay is not the greatest place on the net to get bricks. As you seem to be aware of, it is difficult to get individual bricks from these individual sellers. Having to pay separate shipping from various buyers plus the unreasonable prices can really add up.
Then there's LEGO Shop. Here, you can buy LEGOs directly from the LEGO company. You can individually purchase bricks from Pick-A-Brick, or buy their currently advertised sets. The downside to this is that they obviously do not carry discontinued sets, the selection in Pick-A-Brick is limited, and the prices are unsatisfyingly high, making the bucks add up quickly. Shipping times can be pretty quick and cheap, that is, if they're not currently having any difficulties with their warehouse. If they are, then orders can be delayed by a large amount of time, which has happened to me twice. I once placed an order there which took nearly two months to arrive.
Then, there's Bricklink. You seem to be aware of this website. I like it very much. It is, in many people's opinions, the best source from which to acquire LEGOs. The prices are cheap, it carries almost every piece and set ever released, (even discontinued ones) the tools for finding bricks are useful, and most of the people there are pretty nice. The interface is quite useful, you just have to be familiar with it. Once you get used to it, I'm sure it won't seem so "clunky" to you. For detailed help, enter the chat room. The people there are very nice, and will be happy to you point you in the right direction.
Shipping times vary depending on which area you buy from. Buying from within your country might generate shipping the speed of TLG on their best days. Bricklink, however, is much less likely to have technical difficulties as each order is just an individual seller sending something off to the post office, and has therefore generally been more reliable in my experience.