This is based on personal experience during a short trip to Albania, basically the capital Tirana, and cities in the riviera: Vlorë, Sarandë, and Ksamil. None of the information or links below is promotional or paid advertising.
The country is beautiful but at the time of writing has experienced a massive increase in tourism in a relatively short timespan. That may introduce some annoyances to tourists: it is sometimes difficult to find an English-speaker, while you can certainly find many people who speak Italian. In many places, only cash is accepted as a form of payment.
If you are gluten or lactose intolerant, it is best to buy whatever you need in Tirana before venturing into other cities.
Tips for the lactose-intolerant
You can find soy milk in many shops, in 1-liter cartons, even outside in Tirana and sometimes even in minimarkets. Larger supermarkets may even have rice and almond milk, specially in Tirana. Outside of Tirana we basically only found soy milk, but no other vegetable milk products such as almond yogurt, which you can basically only find in the capital. Smaller cartons of vegetable milk, say of 200ml or 500ml can be found in "bio" shops in Tirana such as BioJu.
If you want your coffee with vegetable milk, you will have to bring your own to the coffee shop. Espresso coffee is served in small cups. You can ask for an espresso in a large cup and ask the barista to heat your own vegetable milk. We found only one large chain of coffee shops, named Mulliri, that serves coffee with soy milk (frappes, etc.) and they are only present at the airport and in large cities.
We could not find cheese made with vegetable milk anywhere. One can ask for a vegetarian pizza without cheese at most restaurants, even small ones: they will give you a weird look but serve it.
Tip for the gluten-intolerant
You can find gluten-free products of the "Schär" brand in Neranxi and other "bio" shops in Tirana, and in some large supermarkets such as the "Conad" in the very center of Tirana.
A great place you must visit is Panja Tirana, which is a gluten-free lactose-free bakery serving bread and delicious cakes, pastries, and icecream.
We could not find any gluten-free bread outside of Tirana. In one bakery, we asked someone to translate for us to Albanian, and the baker did not know was gluten was. There are initiatives such as glutenfreealbania.com collecting resources and trying to raise awareness of this issue.
Tips for vegans
There are few dishes in the local cuisine that sometimes are vegan: falafel (if you order without tzatziki), dolma (vine leaves, but ask, because in some cases they have minced meat) and stuffed peppers (which also in some cases have minced meat). In many places, you can ask for spaghetti with pasta with just tomato sauce, or french fries, or white rice, or many salads without feta cheese that are made with tasty local veggies.
Some restaurants that we tried that had nice vegan dishes:
Finally, let me remark we did enjoy Albania, people are nice and kind, and the mountains and beaches are stunning.
If you go for tapas, the vegan tapas are:
