The result is that if you want to sell, you're less likely to sell below much below the going rate if there are decent arbrigateurs around. If you want to buy, you probably won't have to pay too much of a premium over the market price.
Another point: assuming prices move "smoothly," as arbers get faster they make less and less money. Their profits go in proportion to the "crossing of the spread," so they make more money when the guy who wants to buy is willing to pay a lot more than the guy selling is asking. But if the buyer slowly puts his bid price up and up, the Nash equilibrium strategy for competing arbers is not to wait for a fat payout, because someone else will get it ahead of you -- you snatch up the deal as soon as it appears, when the spread has only just crossed enough for you to make a tiny profit. In the limit of arbitrarily fast arbitrage being detected and acted on, with no cost of executing orders, the arbers make no money at all, and the value traders buy and sell at the same price (paying nothing for the matchmaking service.)
Edit: market making is a different beast, and needs different supporting arguments. Providing a better price than the next guy seems like a worthy public service, though.
And of course this shouldn't whitewash abuses like front-running, which really do make markets worse.
But how can they not find each other? They're in the same market. Too often it seems like it's "I'd like to buy X for $10", but "X is being sold for $9.99 from Y, so I'll buy that up and mark it up a penny as a service instead of having the other guy just buy it directly for that price."
Basically it's making money off of the information asymmetry from having faster machines than the guy who is buying for real. There is almost no risk, the only way to be left holding the bag is if the seller cancels in the 50ish nanoseconds it takes you to buy up the original stock and relist it at the new price". At the end of the day your outstanding risk is 0 unless you've screwed up real bad.
And of course once you have the system in place to do this, it's easy to see a trade for X at $10 and buy up all of the X to relist at $10.00. Here there is slightly more risk since the original buyer may not re-bid at $10.01, but even then as long as you stick to stocks that are moving regularly the risk is small.
No they aren't in the same market. There are a large number of different pools and small exchanges where trading happens. The limitations of physics mean each forum will have different prices at different times. Different forums also have different rules on who may trade and in what way.
HFT Helps arbitrage away these differences. Lowering the spread between differing markets. HFT can also play a part in ensuring correlation of related assets like futures.
Brokers are required to fill at the National Best Bid and Offer price which is specifically defined as the best bid on the national quotation system. However the NQS can only update so fast. Your broker may well know it can get a better price on a specific exchange.
Fidelity will actually keep track of when it gets you a better price and inform you with their "Price Improvement" statistics. Other brokerages will sell your orderflow and let a third party take the difference instead.
Other commenters have addressed geographic stuff, but there's also just weird stuff with other financial products. You might trade currency, others trade interest rate swaps, others trade currency swaps, others trade commodities futures... Sometimes you can "prove" that arbitrage exists by synthetically constructing one product using a couple of others together to infer a price, sometimes you make an imperfect hedge but "good enough".
Value traders shouldn't have to be smart to get the best price available, but someone does have to be smart. Maybe that could be a centralised exchange, but in practice the market does a decent enough job.
The speed race between participants is probably not valuable, but it's the least bad form of market structure that exists. Somebody will do these trades, and everybody wants to, so you need some way to pick winners and losers. Having whoever sets the best price fastest win is less prone to gaming than other structures and rewards competition that drives down inefficiency (you have to do every marginally profitable trade because someone else will snatch it up before it turns into a really great one).
If you could put all the top HFT players in a smoky room where they agreed not to buy new faster microwave lines or high-speed switches, they'd certainly agree to. They're already faster than humans and most banks. They win on that front no matter what. All of this speed competition just changes their rank ordering amongst their peers and costs a lot of money.