How can you get the parent of a UIElement?
Well, if you need to find a logical parent you can just use LogicalTreeHelper in the same manner as VisualTreeHelper.
As for "...and have any thoughts why they didn't just define a Parent property there instead of on FrameworkElement?". Basically, the notion of "Logical Tree" is introduced on the FrameworkElement level. See http://msdn.microsoft.com/en-us/library/system.windows.frameworkelement.aspx (see Remarks) for details of what FrameworkElement adds to UIElement. Here is what it says about Logical Trees:
The logical tree: The general WPF programming model is often expressed in terms of being a tree of elements. Support for expressing the tree of elements as a logical tree, and accompanying support for defining that tree in markup is implemented at the FrameworkElement level. Note however that FrameworkElement deliberately does not define a content model, and leaves that responsibility to derived classes. For more information, see Trees in WPF.