I'd like to post my food restrictions to see if I will have problems when I go to Spain next month. I have celiac (gluten intolerance) so I cannot eat anything containg wheat, rye, barley, malt. No breads, pastas, pastries, anything with flour etc. I also don't eat fish or seafood. Will I have trouble finding things to eat? What dishes should I avoid?

As your restrictions are bigger and not as common as vegetarian, i´ve had to search in the web.
This is what i´ve found:

MADRID HERBORISTERIA LA VENTANA NATURAL Plaza Puerto Maspalomas, 12 Madrid 913865688

MADRID TIENDA ESPECIALIZADA MANÁ Lanuza, 19 Madrid 917255661

MADRID TIENDA ESPECIALIZADA MANÁ Manuel Fernandez Caballero, 1 Madrid 914604712

MADRID RESTAURANTE NO SOLO PASTA Santiago, 3 Madrid 915474203

MADRID TIENDA ESPECIALIZADA DOÑA CELIA C/ Melchor Fdez Almagro, 44, Plaza Carballo Madrid 917390367

MADRID HERBOLISTERIA FELIZ JAVIER C/ Mantuano, 18 28002 Madrid 914151302

MADRID HERBOLISTERIA DOEMI Centro Comercial Carrefour Avda. Guadalajara, 2 28022 Madrid 917758011

MADRID HERBOLISTERIA AMICA C/ General Ricardos, 190 28025 Madrid 917758011

MADRID HERBOLISTERIA BIOCENTRO C/ Virgen del Sagrario, 3 28027 Madrid 914090830

MADRID HERBOLISTERIA BIOCENTRO C. Comercial Alcalá Norte, 414 P. Sotano 28027 Madrid 914083759

MADRID HERBOLISTERIA STOP NATURAL C/ URUGUAY, 3 28016 Madrid 913440692

MADRID HERBOLISTERIA PORTAL Pº ALBERTO PALACIOS, 56. Ctra Toledo Km. 9 Salida 24 a Villaverde 28021 MADRID 915050666

MADRID HERBOLISTERIA BOTICA ECOLÓGICA CB PASAJE DE LA REMONTA, 4 Semiesquina Bravo Murillo 28039 Madrid 9915712008

MADRID RESTAURANTE PUNTO Y COMA TAKE AWAY C/ IBIZA, 52 MADRID 915745089 (This one is near the Retiro park, Metro Ibiza)

In all these places you can buy or eat no risky food for celiacs.There are two restaurants, three speciallized shops, and many herbalist's

I´ve take the information from this page .
("Celiacos" means celiacs,those who have that problem)
There is a list of all the shops, restaurants... for celiacs in Spaim, a list of products you can buy on any supermarkets that are ok, recipies and many more things.

If you click on "en el restaurante" they give you advices about what not to ask.
I copy-paste for you:

"Podría ponerme enfermo si tomo cualquier alimento que contenga trigo, cebada, centeno, avena o los productos derivados de estos cereales. Esto incluye harina, pan, croisants, pastas, empanadillas, croquetas, rebozados, salsas, sopas, pasteles, galletas, bizcochos, malta, extracto de malta, muchos de los embutidos, extractos de caldos.

Los celíacos PODEMOS tomar, carne, pescado, huevos, verduras, legumbres, hortalizas, frutas, arroz, maíz, soja y patata. Estos alimentos deben de ser cocinados sin harina, es decir cocidos, asados, a la plancha, a la brasa o en su estado natural."

You can ask for things such as:

*Carne-Meat
*Pescado-Fish
*Huevos-Eggs
*Verduras-Vegetables
*Legumbres (garbanzos, judías, lentejas...)- Legumes (chickpeas, beans,lentils...)
*Hortalizas (Zanahorias-Carrots...)
*Frutas-Fruits
*Arroz-Rice
*Maiz-Corn
*Soja-Soy

Always make sure they don´t have anything coming from trigo (wheat), cebada (barley), centeno (rye), avena (oats).
You cannot eat:
harina (flour), pan (bread), croisants, pastas, empanadillas, croquetas, rebozados, salsas (sauces), sopas (soups), pasteles (cakes), galletas (biscuits), bizcochos , malta, extracto de malta, muchos de los embutidos, extractos de caldos.
With all of this i think you can have, for example:
-Tortilla española-Spanish ommelette
-Patatas a lo pobre
-Huevos rotos
-Garbanzos
-Lentejas (maybe without chorizo, or stuffs)
-Paella
-Gazpacho...
Hope you have enough information