This sounds like a case where providing users with a dimensionally-modelled reporting schema would be a big win. It would help both with the slow query problem and the super-complicated interface problem.