Reach the Ruse-Giurgiu border crossing by foot or via a local bus and get a car at least over the bridge.
August 2016 - Several city buses run from the centre (near bus/train station) along Tutrakan road to the Bulgarian end of the bridge. I successfully crossed the bridge by foot: approx 30 minute walk. Border guards recommended that you notify the border police before walking. There is a footpath on both sides of the bridge, but in some places this is blocked with construction materials, so you must walk on the road. Be careful and I would advise against doing this at night.
I successfully hitched a ride on the Romanian side of the border, immediately after passport control, as many cars are stopped here.
South towards Veliko Tarnovo
The best spot to stop cars heading south seems to be just before the entrance to the large 'Shell' garage on Route 5. It's an 8-10 minute walk south-west from the major spaghetti junction, on the outskirts of the city. Visible, easy to pull in to and plenty of passing traffic.
If you are hitchhiking with a sign, write "В. Търново", as that is what the Bulgarians and their road signs shorten the name of Veliko Tarnovo to.