All recipes listed need the ingredients + a pick, not sure what the tier of pick does.
You can buy ingredients from the stores in the first city, each store type sells a different category. The stores you can get ingredients from are marked on your map if you zoom in, the actual sandwich store with the recipe guy is NOT.

Normal
Lvl 1. Encounter: Ham Sandwich (Pickle, Ham, Mayo, Mustard)
Lvl 2. Encounter: Ultra Curry-and-Rice-Style Sandwich (Rice, Kiwi, Tomato, Curry Powder, Mayo)
Fire
Lvl 1. Encounter: Pickle Sandwich (Pickle, Olive Oil)
Water
Lvl 1. Encounter: Zesty Sandwich (Jalapeno, Onion, Herbed Sausage, Chili Sauce)
Grass
Lvl 1. Encounter: Klawf Claw Sandwich (?#1, Tomato, Lettuce, Salt, Olive Oil)
Lvl 2. Encounter: Great Klawf Claw Sandwich (?#1, Tomato, Lettuce, Salt, Olive Oil, ?#2)
Electric
Lvl 1. Encounter: Avocado Sandwich (Avocado, Smoked Filet, Salt)
Ice
Lvl 1. Encounter: ?
Fighting
Lvl 1. Encounter: Herbed-Sausage Sandwich (Herbed Sausage, Ketchup)
Lvl 2. Encounter: Great Ham Sandwich (Pickle, Ham, Bacon, Mayo, Mustard)
Poison
Lvl 1. Encounter: Noodle Sandwich (Noodles, Olive Oil, Ketchup)
Lvl 2. Encounter: Great Noodle Sandwich (Noodles, Lettuce, Olive Oil, Ketchup)
Ground
Lvl 1. Encounter: Jambom-Beurre (Ham, Butter)
Lvl 2. Encounter: Great Herbed Sausage Sandwich (Herbed Sausage, Ketchup, Mustard)
Flying
Lvl 1. Encounter: Egg Sandwich (Egg, Cucumber, Salt, Mayo)
Lvl 2. Encounter: Great Egg Sandwich (Egg, Cucumber, Red Onion, Salt, Mayo)
Psychic
Lvl 1. Encounter: Smoky Sandwich (Smoked Filet, Watercress, Vinegar, Pepper, Salt)