Wow...weird that it's cái cây and not cây cây
Yes, but you can think of it like this: tree is a (direct) subclass of object, the classifier for object is "cái", therefore "cái cây".
cái is the generic classifier/counting word and functions like the definite article "the" here, singling out a certain object. It would be redundant to say tree twice.
Yes...but can "cây" not also be used as a classifier?
In this case it would be redundant, you would use "cây" with a stick-like object or a type of tree.
e.g.1 Tôi muốn mua một cây thông = I would like to buy a pine tree.
e.g.2 Ông kia cần một cây gậy mới = That (old) man needs a new walking-stick/cane.