As far as age goes....
Halbarad (now) must be old enough to have an older teenage son. So, he's at least 40 at the time of the Season 3 Frame. We will see him again 10-15 years from now when he arrives for the Battle of the Pelennor Fields, so we don't want to cast anyone
too old. He is one of the Dunedain, so he can appear younger than he actually is (Aragorn is 87 years old when he appears in Bree in LotR, but no one would consider casting an 87 year old actor!) But more to the point, Aragorn is a young teen now, and will grow up in the interim, so we will have to work to make sure Halbarad doesn't become a grizzled grandfather figure in LotR. He can be parental here, but he shouldn't be too old yet.
Gerard Butler was born in 1969 and is 48 years old. Nikolaj Coster-Waldau was born in 1970 and is 47. Any younger suggestions?
Jesse Williams, who plays Dr. Jackson Avery on
Grey's Anatomy, is 36 years old. He also demonstrated in tonight's episode that he does ugly crying rather well, which is relevant because we are killing off Halbarad's son this season and we will have to see him get that news. He has very distinctive eye color, which could be appropriate for the Dunedain.