Handling small dataset of categorical data in Binary classification problem
Is this line of reasoning valid?

You do not have a low number of variables. This number of variables might be considered high, especially considering your low number of entries. As you likely know, scikit-learn is built to handle huge numbers of entries, large datasets. I theorize (not assume) that you have a low number of entries because you cleaned the data too much. You might try another cleaning method that interpolates missing values.
Purely from an academic perspective with statistics and later studies in data science, I suggest that even better than interpolation with the cleaning, you could gather more data.
On another note, no, the reasoning is not valid (see above).

Should I attempt to use complex models and through trial and error I can arrive at the best model in terms of performance and results?

I would, in your position, try all the models you can, with as many different parameters as possible.
I have a dataset of a disease with about 37 features, all of them are categorical variables except for two which are "Age" and "Age_onset". The number of entries is 219.
I am working on developing a binary classification model that predicts whether patients have this disease or not.
The current problem I am facing is deciding what suitable model to select giving the categorical nature and volume of my data.
Now the categorical variables are not high-cardinality, even after applying one-hot encoding the number of variables increases from 37 to 81 therefore it is still considered low in dimensionality. Thus the feature selection methods are not needed.
Moreover, the data is not large in terms of the number of entries (219) and dimensionality (81), therefore there is no need to go for complex models such as neural network or ensemble methods.
This rules out a large number of models and by far I think the best candidate is the Logistic regression classification model.
My question: is this line of reasoning valid? or should I attempt to use complex models and through trial and error I can arrive at the best model in terms of performance and results?
I have gone through many articles and papers with regard to handling categorical data in classification problems, however, my data contains no continuous variables (except for two) and it is not high in cardinality meaning all of the categorical variables have two or three possible answers (highlighted by the number of features after applying one-hot encoding which is 81). So I am not sure that the solutions discussed in those articles applies to my problem.