Lag comes in many flavours.
You have the standard low ping, which feels like you're running through treacle, with moderate-to-large pauses between when you do things, and when they happen.
Packet loss, which is indicated by large freezes, as the client waits for data packets that have been lost en route.
And system performance, which is generally characterised by choppy behaviour. In UO's case, this would be most indicated by mouse movements and animation.
Lastly, there's server-lag, which isn't something that tends to happen these days. Could take the characteristics of the first two, especially on changing areas, but with the defining part that everyone would suffer it.
From the sound of it, I'd say you have one of the first two, relating to a hop on your route to the server. Changing your ISP will only change the first few hops, and the endpoint will be the same.
Consider it like a commute to work, where you run into congestion in the last mile of your journey. Regardless of whether you drive, take the bus, or try a different route, that congestion is always going to be waiting for you.
Run a traceroute to the shard, and see which router along the way is causing the problems.