As soon as we allow relations, we've left the realm of algebras (in the universal algebra sense). For example, a linear ordering is a set $X$ together with a binary relation $<$ such that [stuff]; a linear ordering is definitely a set with structure, but that structure isn't given by functions, so it's not an algebra.

There are also structures that mix relation and function symbols, such as ordered groups/rings/fields. And something like a topological group is even further from this picture, since the "additional structure" (= the topology) exists at a "higher level" than just functions/relations on the underlying set.