Design an amplifier with maximum voltage gain
Av = vo / vi = gm*RE1
I have a feeling this result doesn't seem right.

Your error here is that in this circuit vgs and vi are not the same thing. The input voltage is applied across the combination of the transistor's gate-source branch and the source resistor RE1.

I'm looking on the manufacturer's datasheet for the MOSFET I'm using, and there is no value for the transconductance parameter...

I'm not sure which parameter you're looking for, but transconductance itself is given as a specification:

However, as you see, the value is only specified for one particular operating condition, and is only given as a typical value.
Finally, a couple of hints:

Recognize that the first stage is a source follower (assuming we work with MOSFETs instead of BJTs), not a common-source stage. So provided you choose reasonable values for RE1 and RC1, the voltage gain will simply be 1.

When you get to the 2nd stage, realize that if C4 were absent, then you would not need to know gm to get the approximate gain of the stage. However, with C4 present (assuming it's chosen to give a low impedance at the operating frequency) this goes out the window and I think you will need to have a maximum limit on gm to be able to guarantee no saturation. Since that spec (or the equivalent, max \$\beta\$ on BJTs) is rarely given on real-world devices, the problem itself doesn't seem to be well-designed.

When you talk about saturation, you're talking about a large-signal effect. Small signal models will only take you so far with predicting this behavior. To  answer this problem for the real world, you'd want to build a SPICE model and do some tolerance analysis to be sure you don't have saturation with worst-case variation of all your components.