Off the top of my head, the most common type of sandwiches are: ham and cheese ( yes you guessed that one !! ), leberwurst and eggs, prociutto and butter, prociutto and tomatoe, tuna and lettuce, chicken or turkey and tomatoes, salami and cheese , pastrami and pickles and the most common types of bread for these are pita bread, pebete, frances, figaza de manteca. Any standard bar or restaurant serves these
The best deli stores prepare sandwiches with whatever type of cheese and coldcuts that you want.
Also most baker stores sell sandwiches de miga ( very popular for birthdays and parties in general ) with a lot more combinations: palms, olives, peppers, ham, prociutto, cheese, cream cheese, pastrai, salami, pickles, eggs, lettuce, tomatoes, turkey, corn, eggplant, artichokes, pineapple, roquefort cheese, mushrooms, tuna, anchovies.
As for pasta, I only like it hand made so I only go to places where they make their own pasta. In general at most italian restaurants you can get ravioli, gnocci, caneloni, capeletti, torteletti, fettucine, vermicelli, spaghetti, lasagna, with different fillings and in different sizes, with different sauces.
I am very curious as to where you are getting this bland stuff, can you name some places?
nik