This list is partial and possibly biased. If you want the full list, take a peek at http://www.openbsd.org/plus56.html or look up the source-changes archives.
ALTQ traffic shaping removed from PF. No more oldqueue tricks, you will have to move to the new system.
sendmail is due to be removed from the base system (gone in 5.7), smtpd is the default mail transport agent (MTA). The legacy sendmail MTA will be available as a package. Yes, there is a /usr/sbin/sendmail binary; it's a symlink to /usr/sbin/mailwrapper.
Kerberos has been removed from the base system. Kerberos support will be available via a package.
The BIND (named) name server is about to be removed from the OpenBSD base system (gone in 5.7). Its replacement comes in the form of the two daemons nsd(8) for authoritative DNS service and unbound(8) for recursive resolver service. If you need the real BIND past this versino, install the isc-bind package.
The base system httpd, a forked Apache 1.3, has been removed in favor of nginx as the system HTTP(s) server. Apache 1.3 will be available as a package.
The installer no longer supports FTP, network installs via HTTP only. If you run an internal mirror, your life just became easier.
OpenBSD 5.6 is the first version with LibreSSL (OpenBSD's cleaned-up fork of OpenSSL). Only user-visible change: openssl(1) moved to /usr/bin.
userland ppp(8) and pppoe(8) removed. Move to kernel ppp with pppd(8) or if you need L2TP, PPTP and PPPoE, have a look at npppd(8).
tcpwrappers, with libwrap and tcpd has been removed. Convert any /etc/host.deny or/etc/host.allow entries to PF rules.
The old-fashioned rmail and uucpd have been removed from base. If you want the functionality, install the port or package.
Weak and broken hashes, modes and ciphers have been removed from sshd(8) default config. Some older clients may need upgrading (or you can re-enable the weaknesses in your config).
Configuration files for non-default daemons moved to /etc/examples, others such as pf.conf reduced to bare minimum out of the box.
relayd filtering grammar changed, now has match, block etc much like the PF grammar
Java became available again on i386 (32 bit) soon after 5.5 release with unbroken package. Oracle still does not care one way or the other
IPv6 configuration defaults changed: -inet6 is the default, IPv6 addresses (including link-local) set only when explicitly enabled, global accept_rtadv sysctl removed.