First, you need to get a bit of an understanding of vast variety of Rums. Unlike Tequila, Bourbon, and many other spirits, there are no real "rules" on rum production, other than it has to be make with sugarcane as a base. I would suggest getting a bottle or two of the representative styles and then you can narrow down your tastes.
Rhum Agricole (Martinique) is the most unique in flavor, it must be made from locally grown fresh sugarcane juice, whereas most other rums are made from molasses. It has a very grassy taste, quite unique. Rums from Jamaica tend to have the most flavors if they are made in the traditional method using pot stills and Dunder (muck left over from the distillation process that is left out to rot in an open pit).
Those two styles tend to be the ends of the spectrum. In between you will find "Spanish styles" (Cuba, Puerto Rico) that are made using a column still and aged a bit and carbon filtered, so they tend to be lighter in flavor. "British styles" tend to dominate the market (Barbados, Venezuela, Virgin Islands etc) and are made with molasses and various combinations of pot and column stills. Then there are rums from the South Pacific, India etc. Rum is made practically everywhere.
Ageing is far over emphasized as a measure of quality or taste and is more a marketing gimmick. In addition, the rules vary on what you can claim for "age". Most rums are blends of different ages and processes, as well as being aged in different barrels in different climates. What type of barrel you use (the most common is used American oak bourbon barrels) and where it is aged has a huge impact on the flavor. Color also means nothing as regards to quality, Bacardi silver for example, is aged 2 years, then carbon filtered to remove the color and all dark rums like Meyers or Pussers are colored with caramel.
You will find many of the better rums, typically from smaller producers, are over-proof (can also be called barrel proof or navy strength).
Most of the suggestions already mentioned are good, but it does depend on how you are going to drink the spirit. A rum that can stand up to a tiki drink won't sip as well on ice for example. One of my favorite sipping rums is Barbancourt from Haiti, it really is exceptional with a splash of club soda and lime.
