A 401(k) client is starting a NQDC Plan with both deferral and employer money, and wants me to administer it. Their attorney will be preparing the "documents". They want me to give them an estimate on fees. What work will be involved besides an annual valuation on the assets held in the Rabbi trust?

Depends on the plan design. The plan could be almost the same as a 401(k) plan. At the other extreme, it could be more like a bank account with annual deposits. The plan could also be more like a qualified defined benefit plan. You might also want to consider that a mistake could have more serious tax consequences and be impossible or more difficult to remediate compared to a qualified plan. Finally, ask who will be responsible for the securities law compliance and how that will affect your work.