I feel like it's like pointers.

"Variable" refers to the label, i.e. a box that can contain anything (like *ptr is a pointer to [something we dont know anything about])

Immutable describes the contents, i.e. the stuff in the box cant change. (like int* ptr describes that the pointer points to an int)

Rust makes it very obvious that there's a difference between constants and immutable variables, mainly because constants must be compile time constants.

What do you call it when a variable cant change after its definition, but isnt guaranteed to be the same on each function call? (E.g. x is an array that's passed in, and we're just checking if element y exists)

It's not a constant, the contents of that label are "changing", but the label's contents cant be modified inside the scope of that function. So it's a variable, but immutable.