I'm using Ubuntu 16.04 and there's no fglrx!

The publishing history on Launchpad indicates the package has been deleted for 16.04:

Removed from disk on 2016-03-03.
Removal requested on 2016-03-03.
Deleted on 2016-03-03 by Martin Pitt
(tjaalton) there will not be updates any more, incompatible with new X.org ABI, free driver is good enough now

You could post a bug on Launchpad if you feel the open source driver isn't good enough.

The Release Notes for 16.04 has more information:

fglrx

The fglrx driver is now deprecated in 16.04, and we recommend its open source alternatives (radeon and amdgpu). AMD put a lot of work into the drivers, and we backported kernel code from Linux 4.5 to provide a better experience.

When upgrading to Ubuntu 16.04 from a previous release, both the fglrx driver and the xorg.conf will be removed, so that the system is set to use either the amdgpu driver or the radeon driver (depending on the available hardware).

In a mailing list discussion, it's suggested that people who really need the fglrx driver might have to continue using 14.04 until the open source driver improves:

AMD dropped support for their proprietary-blob fglrx video driver so it can't be included in 16.04 LTS. The last release AMD did can not be used because it is incompatible with the newer x.org display server. Most people will be able to the use the open source AMD video driver, but there are a few applications (certain graphics-intensive games, bitcoin mining) for which it is inadequate. Folk who rely on such applications might choose to remain on 14.04 LTS until adequate support lands in the open source AMD video drivers.

Related:

• Ubuntu Is Deprecating fglrx (Catalyst) In 16.04 LTS - Phoronix

To start Steam without fglrx, type this in Terminal:

LD_PRELOAD='/usr/$LIB/libstdc++.so.6' DISPLAY=:0 steam

Terminal has to be active, for small games (Stellaris by my own) it's practicable.