I have noticed that NPCs try to take a straight line to their next task. This is leading to NPCs jumping over hedges, or getting stuck on fences.

Suggestion. Let us define "nodes" on our paths (probably at each corner) and connect them together to define where our paths are. Then, instead of walking in a straight line, work/utility NPCs should check if a path is closer than their next job, then travel the path from node to node until they arrive.

A waypoint tool would be really nice. I've had issues with path-finding too.

Jumping off small cliffs, climbing chests and even getting teleported to the nether because they thought the portal was a good path to take.

You could do it by modifying the work order to allow adding arbitrary blocks as a "job", where they simply get there to complete it and then just move onto the next job.

I gave the source code a look and that definitely looks like it could work (IMO)

I like the sounds of that. I usually spend ages modifying paths for couriers so they don't get lost or stuck but it's a fair bit of work.

That sounds very similar to the existing pathing AI for the Traders, unless I'm mistaken.

Doable, indeed. Will probably add that feature to the current order items, rather than making a new one.