Najlepiej aby nie wysyłać ponownie całego zapytania do serwera
O ile nie posortujesz wyników w JS, to będziesz musiał wysłać żądanie na serwer tak czy siak.
A jeśli chodzi o zapytanie do bazy, to nie widzę w tym nic złego (pod warunkiem, że zapytanie nie wykonuje się 10 sekund). Po prostu przesyłasz parametr sortowania (np. GETem) i podstawiasz do zapytania SQL.
Czy zwrócone dane z php powinny znajdować się w tabeli czy mogą równie dobrze być w divach?
To zależy, jakie dane zwracasz. Wybierasz taki element, aby było w miarę semantycznie poprawnie. Może to być np. tabela albo lista.