Here's some notes on how they apply to leased lines.
1) HDLC is simple, it requires nearly zero configuration, and has low overhead. It's also the default. Most simple WAN installations use this. You likely don't have any reason to change.
2) PPP will also work on a leased line. Configuration is relatively simple. There's a negotiation process when the line comes up, but that's only a second or two. After that, the overhead/speed is comparable to HDLC. PPP with multilink enabled will allow you to do link fragmentation, which is important if you have fractional T1/E1 service and you need to constrain packet sizes to control jitter for VoIP and the like. PPP is also interoperable with almost any vendor's equipment (Cisco's HDLC implementation is proprietary).
3) Frame-relay can be configured on a leased point-to-point line, but there's little point. The only legitimate reason I've ever seen to build a P2P line as frame-relay is to set up layer 2 bridging of multiple VLANs over one serial link using seperate PVCs and subinterfaces. Configuration complexity is moderate. Most of the QoS features it offers (except for fragmentation) are not relevant to a P2P installation, only when connecting to carrier networks. Overhead is comparable or very slightly higher than HDLC or PPP.
4) ATM requires special equipment and interfaces that you likely don't have. Configuration complexity is moderate. ATM imposes a ridiculous amount of overhead when compared to HDLC or PPP due to cell sizes, thus reducing available bandwidth. You really don't want to use ATM for this installation.
