Building the table server-side and sending all the HTML to the client, or sending the table data to the client and then building the table, are really the only two ways of approaching this problem, as you say. Tabels suffer badly from blocking/slow loading issues as they are rendered, especially large and complex tables. Why not send the data across in a structured way, and then build the table out of CSS (using DIV tags) instead of HTML table tags? That should render the table a lot more faster. It's worth experimenting.
Design Patterns can help when you are faced with a decision like this. Take the Model-View-Controller pattern, more commonly known as MVC. It tells us that the server should restrict itself to business logic, hence to business code. An example of business code is a CFC that returns data in the form of an array.
To display the data as a table requires presentation logic and presentation tools. That responsibility usually falls on the client. The browser is typically the client equipped to render the data in visual form.
You could, for example, get the CFC to return an array in the default JSON format. The client could then use jQuery to convert the JSON array into a table. A quick search on the web produced the following jQuery tools: datatables, jqGrid and jsonTable.