I eat "Paleo", which is to say that I don't eat any grains (no bread, no pasta, no flour at all), and I don't eat dairy (this is the strictest version).
You're essentially eating Meat, Vegetables, Fruit, Nuts and seeds.
I will tell you that if you make the switch to this sort of diet, and you don't limit yourself initially in calories, you'll feel different. If you're used to eating a lot of starchy foods, getting "food comas" after lunch, etc... you'll notice a difference in your blood sugar levels.
I think that trying to by "gluten-free" substitutes of foods that typical have gluten is sort of silly. They're not even real "foods" in my opinion. They're food products.