In the Gargano, visit the old cities of Monte Sant'Angelo, Lucera, Manfredonia, and San Severo, and the Padre Pio sanctuary of San Giovanni Rotondo. Vieste is near to Italy's newest national park, the Foresta Umbra, and is the holiday capital of the Gargano.
Trani, along the coast, features an old settlement right around the harbor with seafront Cathedral dedicated to San Nicola Pellegrino. 18th century palaces like the Caccetta, the Quercia end the Bianchi give you a good idea of Puglia's Romanesque period. The Swabian castle of Trani was built by Federico II between 1223 and 1249, and was recently used as a prison.
Bari is a port city with an interesting old center. You can get the ferry to Greece from Bari.
You can also get ferries from Brindisi, but it's a less interesting town.
Trulli country starts in Alberobello, where there are more than 1500 of the strange, conical houses. You can rent one for a week to get the feel for this interesting part of Puglia. Locorotundo and Martina Franca are also interesting cities to visit. Trulli Hotels
Lecce is blessed with a soft limestone so easy to work that Lecce became the center for ornate architectural ornamentation, called the barocco leccese, or Leccese Baroque. Lecce is a great town to walk around in, and its restaurants offer abundant fine food.
On the Salento Peninsula, the fishing village of Gallipoli has a nice port area and interesting historic center. Another nice seaside town is Otranto, known for its beautiful coast. Otranto was an important centre of the Byzantine dominion in Italy, and had a Greek bishop. A visit to the duomo is a must.
Santa Maria di Leuca is the end of the world, you might want to visit il Ciolo, a deep canyon scoured by the sea.
Find out more about what to see in Top Places to Go in Puglia.