Must all CNNs and RNNs not have a fully connected layer in order to be considered as such?
Not quite sure about RNN &amp; LSTM (and it always depends on the task), but for CNN the answer is clearly no; CNN routinely include FC layers. Quoting from the highly popular (and recommended) Stanford course CS231n: Convolutional Neural Networks for Visual Recognition:

ConvNet Architectures
We have seen that Convolutional Networks are commonly made up of only
three layer types: CONV, POOL (we assume Max pool unless stated
otherwise) and FC (short for fully-connected).

You can easily verify that this is the case for practically all popular CNN models for computer vision in any relevant exposition (e.g. Illustrated: 10 CNN Architectures).
In fact, the all-convolutional NN (i.e. without FC layers) is considered a special case: see Striving for Simplicity: The All Convolutional Net.