Have you thought about the Paleo diet? It’s what I usually recommend as a starting point because being so popular there are loads of recipes online - which makes it easier for people to get into and less likely to fail 
1 Like