As you mentioned, the memory size and the program size are the biggest two constraints. There's no space for a garbage collector, and everything has to be allocated on the stack. It turns out that it is possible to make the entire thing stack-free. The two biggest hurdles are function closures, arrays, and recursive data types.
Function closures are typically allocated on the heap since it's possible to return functions from other functions. The solution is to include the closure as part of the function type, which means that they can then be allocated on the stack. Arrays are a bit more tricky to allocate on the stack. My solution is to statically size arrays with type level natural numbers, which means that the sizes are known at compile time.
Recursive datatypes are a problem that I have not dealt with yet. In most Arduino projects recursive datatypes are not really used, so I just don't allow them. It might be possible to use type level natural numbers to put a bound on recursion depth. Another idea I had was to use run-timed size datatypes. For example, let's say you have a function F1 which calls F2. The frame pointers for their corresponding frames are at S1 and S2. When F2 returns a value of size N, the solution is to copy the value to a scratch space, return to F1, decrement the frame pointer, and then copy the value back into the stack frame. I'm not sure if this is really suitable for embedded systems since it's a lot of code/machinery which takes up precious program space.
Rust is a great language which can work around these issues due to its linear types. I'm looking forward to using Rust once it starts to support the Arduino microcontrollers.