For instance, will hard water really change the taste that much?
Short answer: yes.
Longer answer is more complicated; sufficiently hard water will cause all sorts of hilarity during the brewing process. Remember, this is dealing with organic chemistry and living things doing our bidding, therefore difficult (for me) to fully understand. There's a great resource available from the Brewer's Friend that I'd strongly advise reading.
A good resource on water chemistry is sections 15.0 to 15.4 of Palmer's How to Brew: http://www.howtobrew.com/section3/chapter15.html
High bicarbonate (CO3) water has a higher alkalinity. Using water high in bicarbonates to make a pale beer such as Pilsner will yield a 'harsh' bitterness. This type of water tends to favor dark beers made with roasted grains - the roasted grains are acidic, and balance the alkalinity (think Dublin water for Guinness).
High sulfates (SO4) (such as in Burton on Trent) tend to accentuate hop flavor and perceived dryness.
Sodium (Na) adds 'roundness' and accentuates malt flavors.
Absolutely yes. There is a reason why breweries tend to be located at specific places, and there are examples of breweries that relocated changing the taste of their beers as a result.