The best piece of advice you have received is "..don't give them advance notice", and hope that no one at the shop is a member or guest here!! I like REGs approach - call from a block away, ask for an update, and then pull up to finish the conversation in person while loading. Keep everything friendly and professional, just cannot continue to wait for them to have time to work on your ride, it's been almost 4 years, and going to make a change.
Best of luck.