In case anyone was looking for a C# approach, I was able to use reflection and come up with the following:
public IEnumerable<String> GetColumnsFor<T>()
{
    return typeof(T).GetProperties(System.Reflection.BindingFlags.Public | System.Reflection.BindingFlags.Instance)
        .Where(x => !Attribute.IsDefined(x, typeof(System.Xml.Serialization.XmlIgnoreAttribute))) // Exclude the ignored properties
        .Where(x => x.DeclaringType != typeof(sObject)) // & Exclude inherited sObject propert(y/ies)
        .Where(x => x.PropertyType.Namespace != typeof(Account).Namespace)  // & Exclude properties storing references to other objects
        .Select(x => x.Name);
}
It appears to work for the objects I've tested (and matches the columns generated by the API test). From there, it's about creating the query:
/* assume: this.server = new sForceService(); */
public IEnumerable<T> QueryAll<T>(params String[] columns)
    where T : sObject
{
    String soql = String.Format("SELECT {0} FROM {1}",
        String.Join(", ", GetColumnsFor<T>()),
        typeof(T).Name
    );
    this.service.QueryOptionsValue = new QueryOptions
    {
        batchsize = 250,
        batchSizeSpecified = true
    };
    ICollection<T> results = new HashSet<T>();
    try
    {
        Boolean done = false;
        QueryResult queryResult = this.service.queryAll(soql);
        while (!finished)
        {
            sObject[] records = queryResult.records;
            foreach (sObject record in records)
            {
                T entity = entity as T;
                if (entity != null)
                {
                    results.Add(entity);
                }
            }
            done &= queryResult.done;
            if (!done)
            {
                queryResult = this.service.queryMode(queryResult.queryLocator);
            }
        }
    }
    catch (Exception ex)
    {
        throw; // your exception handling
    }
    return results;
}