I've done jqGrid before in Apex with @RemoteActions and it's definitely the way to go. I think with Ajax toolkit and SOAP, you'll have too much XML bloat compared to JSON for large sets of records.

As for loading all 78000 records, I would say you should stick to the limits of loading 2000 records at a time and than breaking those into further subsets of 100 records / page on the client side.

To pagination with large record sets I would recommend using the standard set controller for pagination. Just make sure to include an order clause to keep the records returning in the same order.

Than load the next 2000 records in each subsequent call. And reduce the number of records you return from the server to speed things up in between 'set loads' as you get to the end of each set and need more pages.

You can also count the number of records and return it in a complex object from the @RemoteAction to keep your pagination accurate:

public class returnType{
  List<sObject> objects {get; set;}
  Integer totalRecords {get; set;}
  Integer nextPage {get; set;}
  Integer lastPage {get; set;}
}

UPDATE

Ok using the SSC to maintain pagination (at least this is the way I would do it with jqGrid:

@RemoteAction
global static returnType pagination(Integer pageNumber){
   ApexPages.StandardSetController ssc = new ApexPages.StandardSetController(Database.getQueryLocator([SELECT Id FROM sObject ORDER BY Id LIMIT 50000]);
   ssc.setPageNumber(pageNumber);
   ssc.Pagesize(2000);

   returnType retVal = new returnType();
   retVal.objects = ssc.getRecords();
   retVal.nextPage = pageNumber + 1;
   retVal.previousPage = pageNumber - 1;

   return retVal;
}

I don't have my original code in front of me, but generally, the SSC should be re-instantiated with each call. As for getting past 50k records, and to your total set, the query locator should continue to the end of the set reguardless of size taking the larger records towards the end of the set as you get to the end of [0..n-1] pages.

In practice I would use an ORDER BY clause to ensure your records are consistently returned in the same order to ensure that your getting all results.

Seems you are using SOAP APIs, where by default the max records returned are 500, which could be uplifted to 2000. Best would be to use "queryMore" to load the records. Here is a post from salesforce docs with good code samples for the same: http://www.salesforce.com/us/developer/docs/api/Content/sforce_api_calls_querymore.htm