The DataGridView has something called "virtual mode". Instead of databinding (and the overhead), it simply requests the values that should be on-screen. That means that you can display the first records immediately after loading them. There's a walkthrough[^] on MSDN.
For it to work nicely, you'd load your data on a separate thread, using a reader, and synchronize every now and then (every second or every 100 items).
Bastard Programmer from Hell
If you can't read my code, try converting it here[^]