What is being described is a basic tree walking interpreter. If this is new to you, and you come from the OO world, there is an extended description in https://craftinginterpreters.com/a-tree-walk-interpreter.htm...
In the FP world this very very (very!) standard. A tree walking interpreter is one hop away from FP basics. The tools you need are tools that beginners learn in their first few weeks:
1. algebraic data types to represent the abstract syntax tree; and
2. structural recursion (usually implemented via pattern matching) to walk over the algebraic data type and interpret it.
Using generalized algebraic data types is a small extension if you don't want to box your result types (which addresses the comment "Python's duck typing definitely helps make your life simpler, because otherwise you need to be careful about designing what all the Eval()s return." in the OP.)
I don't understand why OP says conditionals or control flow are difficult. Those have been straightforward in the interpreters I have created.
Overall, I feel there are standard techniques for this kind of thing, in both the OO and FP worlds. In my experience the FP world is more precise with terminology, and I think this is beneficial.