Where it's most obvious, which will almost invariably be the foreground as that's biggest in frame and naturally shows the most perspective change.
There's some barrel distortion in that image too. It'll look better with that sorted first.
I agree with Nod, at least to an extent. It's easy to over-correct and make things look unnatural. After a certain point, it's better to just leave it.. It also depends on the type of shot - if you're shooting architecture or real estate, then verticals should be straight and true, but for say street stuff I'd correct any (unnatural) lens distortion, but leave the (natural) perspective effect alone.