I think you actually provided a good start for the correct answer right in your question (you just need the correct syntax). I had this exact same problem, and putting DISTINCT in a sub-query was indeed less costly than what other answers here have proposed.
select a.FirstName, a.LastName, v.District
from AddTbl a
inner join (select distinct LastName, District
from ValTbl) v
on a.LastName = v.LastName
order by Firstname