Historically, Vanguard has had the lowest fees/expense ratios on index funds (I don't remember the exact number at this moment). I see where Fidelity has dropped some of their expenses, but you sometimes have to keep an eye on Fidelity. They will sometimes voluntarily cover a portion of a fund's expenses, but then they can stop doing that in the future. When you go online to check out their funds, they disclose this information.
A couple other points:
-It's hard to properly diversify when you are first starting out. If you try to buy multiple funds, your returns can be held down by low balance fees. The perfect solution is a Fund of Funds, which is basically a mutual fund that buys shares in other mutual funds. I especially like Vanguard's LifeStrategy Funds. If you invest in one of these funds, you are simultaneously investing in a Total Stock Market Index Fund, a Total International Stock Index Fund, an actively managed asset allocation fund, and a total bond market index fund. Fidelity also offers Funds of Funds, but they usually tack on a small expense for bundling the individual funds together (Vanguard does not).
-Here are just a few reasons that I use Vanguard as my "home base" for investing: because of their low fees, Vanguard's money market funds are a good place to park your money until you're ready to invest/use it (my loan money is currently sitting in one); Vanguard pioneered index funds and usually have the lowest fees (the primary determinant of an index fund's success); also Vanguard only charges $35 to buy funds from other companies (I believe Fidelity charges $75).
All that being said, Fidelity is certainly a more than satisfactory choice (and once I have more money, I will certainly invest with them). Just be sure you are investing in their no-load funds and keep an eye on expenses.