Learning Traditional first with the goal of learning both
This is a difficult questions, since most people are quite religious about this topic. For some reason they prefer one over the other and say this one is the best one to learn first.

Learning Chinese characters takes a huge effort and most need many years for that, however once you know one set learning the other one is relatively easy.


  Wiki says that the Jianhuazi zong biao lists 350 individually
  simplified characters, 132 generalisable simplified characters and 14
  simplified radicals. All other simplifications are simply variation of
  the latter two simplifications (thousands of them, but applied in a
  standard and predictable way), or standardising on a more simple
  variant in place of a more complex variant of the same character.
  
  This means that there are 500 characters that are significantly
  different between the two sets, and the rest appear to me to be easy
  (e.g. 説 = 说, 錢 = 钱, etc.)
  
  So the extra effort one needs to invest into learning traditional
  characters after knowing the simplified set (or the other way around)
  amounts to learning about 500 characters. Since one should aspire to
  knowing about 3000 as some sort of arbitrary standard of literacy,
  this doesn't strike me as a huge deal.


Source: http://www.chinese-forums.com/index.php?/topic/14713-learning-hanzi-the-eternal-dilemma-of-simple-or-traditional/page_st_20_p_150151&amp;#entry150151

Also take a look on this page: http://www.chinese-forums.com/index.php?/topic/25651-learning-traditional-characters-after-studying-simplified-for-4-years/#entry214033

The 10 hours mentioned on the last page is a bit optimistic, but it is certainly quite manageable once you already know that many characters.

Also more or less all educated Chinese from the mainland can read traditional characters, and more or less all educated Chinese from Hongkong and Taiwanese people can read simplified characters. Not because they explicitly learned them, but due to exposure for example as subtitles from movies, songs or the internet. Once you have reached a certain level it's not that difficult.

What to choose first depends on your personal situation. I would first study what you think you will encounter most. For example if you often plan to go to Taiwan or Hongkong or especially want to view Taiwanese or Hongkong soap operas or movies (while learning Chinese most people are better at reading than listening, so the subtitles are of huge help) or have friends from Taiwan or Hongkong, start with traditional characters. If you on the other hand think you'll more often encounter simplified characters, choose simplified characters.