I managed to get reasonably good looking levels by using the following algorithm, based on a square grid:
First, create a set of rooms. Random parameters will define the size of rooms and their numbers. An adaptive algorithm could even define some zones that are made of large hallways, and others of very small rooms.
Then, you need to make sure that all rooms are connected to each other. For this, run a pathfinder to dig corridors (let's say, A*) in between each pair of rooms, giving a random chosen weight to existing spaces (rooms or other corridors) compared to space not yet carved (the walls). If the difference in weight is small, then digging new corridors will be reasonably cheap, and the algorithm will make many corridors in between rooms, with many possibilities to go from a place to another. If the difference in weight is high, then the algorithm will prefer going through existing rooms and corridors, making the paths more tortuous, and with fewer choices to reach a certain destination.
This allows you, from a small number of parameters, to create very different looking levels, from sparse massive halls with small corridors linking them to a hive looking maze of closely interconnected chambers.
Here is an example of a generated level.
Based on this algorithm, you could add wall decoration that depends on the zone, make corridors smaller or larger, make special rooms, and so on.