Personally, I suggest you think about quality first and price second.  Not
saying you're not, just trying to keep things focused on what is important.

You should chose a high performance regulator with a brand name you know,
that is common in the area where you live and where you will be diving.
Most people have their regulators serviced annually.  It's a lot easier to
handle that if it can be done locally than if your regulator has to be sent
out once a year.  Most warrantees require it.  When traveling to dive,
sometimes things don't work just right.  A regulator that can be serviced
where you might be diving will save you from some problems like you have
already experienced with rental equipment.

Some warrantees cover parts required for annual service.  Be sure to factor
service and parts into your overall purchase decision.

I probably have a half dozen or so regulators.  Most of them are older US
Divers regulators, all of which have given me very good service over a lot
of years.  They don't seem to be favored by today's more advanced divers,
but their history suggests you would not go wrong with any of their high
performance models.

My current regulator is a Scuba Pro.  Scuba Pro regulators have been among
the top rated regulators for quite a few years.  I'm not sure they qualify
as mid priced, but I am sure they qualify as quality.  At least consider
them in your regulator decision.

You're going to get recommendations for Apex/Apeks (I can never figure which
is which).  They have an excellent reputation here and in Europe,
particularly among those that dive in water cold enough to worry about
freeze ups.  last I remember, they were reasonably priced and highly
regarded.  If I had to guess, I would guess you'll wind up with one of them,
but that's only a guess.  I don't use them.  My opinion is based entirely on
what I've heard from others.

Aside from the brand, there are a few things worth keeping in mind:
1. Consider where you will dive.  If it's cold water, your choice is likely
to be different.
2. Consider the configuration you'll prefer.  Some of us here, including me,
experimented with elements of a configuration known as DIR (Doing It Right).
It's a tech oriented configuration that includes things like a primary on a
5-7 foot hose (routed differently) and an alternate second stage attached
under the chin by a bungee or similar necklace arrangement.  I'm not
currently using the long hose, but I did retain the necklaced alternate.  In
an emergency, I will use the alternate and donate the primary (same if I
were using the longer primary hose).  Do some research on the DIR system
before you buy.  You may want to chose equipment that works well with it, a
smaller sized alternate, for example.
3. No matter what second stages you chose, go for a high performance first
stage.  If you have to share gas with someone, chances are that both you and
the other diver will be breathing heavily.  Make sure your first stage can
handle to heavy breathing divers at depth.
4. Do not let anyone talk you into buying a high quality first stage and a
low quality alternate.  Remember, the alternate will be used in emergencies.
When can it possibly be more important to have a good regulator  than in an
emergency.  If you adopt at least part of the DIR equipment configuration,
you'll be using that alternate while someone else uses your primary.  Think
about that.

As for gauges, I recommend a computer.  More specifically, I recommend a
nitrox capable computer.  Chances are good that, eventually, you'll use
nitrox for most of your dives.  You can save money later, by getting the
computer you'll want then, now.  I like Aeries, Oceanic and Genesis.  I
prefer the round ones that look a bit like a hockey puck, in a standard
size.  The standard round ones are not only less expensive, they are more
versatile.  They'll fit in pretty much any console or wrist mount.  If you
do with one of these computers, consider spending the money for one with two
buttons rather than a one button model (which both of mine are).  They don't
work any better during the dive, but the  second button makes selecting
options, changing nitrox blends, etc. a lot easier.

Like many experienced divers, I don't care for air integrated computers.  I
prefer to use a contents gauge to monitor gas and a computer to monitor
other aspects of my dive.  You may feel differently.  If you do go for an
air integrated model, pay particular attention to the conditions under which
the computer shows you various information.  Some will display remaining
time based on what the computer considers most critical, some will alternate
displays during the dive and some will let you chose what you want to see,
when.  Make sure you understand what will be displayed and what it means
before you buy.  It's too late once you've made your purchase.

I do not like Suunto computers.  Their algorithm is too conservative for my
taste and they way most of them handle nitrox is, in my opinion, a good
reason to buy something else.  If you consider one, please spend some time
to understand how their PPO2 and MOD calculations vary from what other
computers show under the same conditions and how they calculate O2 and N2
limits when you reach PPO2s above 1.4 ata.  I've been told the Vytec (sp?)
uses a different, better algorithm than other Suunto models.

One last note on computers.  Give some thought to how you'll mount a
computer when deciding what to purchase.  I already mentioned that the ones
I have are very flexible.  They'll fit in the standard gauge hole in pretty
much any console and in a commonly available, and inexpensive, wrist mount.
A few years ago, when I had a high pressure leak in my own equipment, it was
a simple matter to pop my computer out of the console, put it into a wrist
mount and use the contents gauge from the backup regulator I take on trips.
You can't generally do that with an air integrated computer or, for that
matter, with one that isn't a standard shape and size.  Generally speaking,
if you start a series of dives, in a day, or over several days, with a
computer, you need to continue to dive with that same computer.  If you
can't, the general rule is to sit out for 24 hours before diving with gauges
or a different computer.  If I had not been able to move my computer when I
swapped my contents gauge, I would have spend a day of very expensive dive
travel, watching others do what I paid to do.

Good luck in your search for equipment.  When it's all said and done, please
let us know what you chose and why.

Lee

 Check out the Sea Elite brand at Diver's Supply.

 http://www.diverssupplyusa.com/index.asp

 I had that as my first reg, and -loved- it.

 I since "upgraded" to Scubapro, but primarily because I got it at 50% off.

 The reg was semi-permanently loaned to another Rec.scuban.