¿Encontrar registros únicos, ordenados por campo en asociación, con PostgreSQL y Rails 3?

La consulta que está buscando debería tener este aspecto:

SELECT user_id, min(created_at) AS min_created_at
FROM   cards
WHERE  company_id = 1
GROUP  BY user_id
ORDER  BY min(created_at)

Puedes unirte a la tabla user si necesita columnas de esa tabla en el resultado, de lo contrario ni siquiera las necesita para la consulta.
Si no necesita min_created_at en el SELECT lista, puede dejarlo de lado.

Debería ser fácil de traducir a Ruby (que no se me da bien).

Para obtener el registro de usuario completo (como deduzco de tu comentario):

SELECT u.*,
FROM   user u
JOIN  (
    SELECT user_id, min(created_at) AS min_created_at
    FROM   cards
    WHERE  company_id = 1
    GROUP  BY user_id
    ) c ON u.id = c.user_id
ORDER  BY min_created_at

O:

SELECT u.*
FROM   user u
JOIN   cards c ON u.id = c.user_id
WHERE  c.company_id = 1
GROUP  BY u.id, u.col1, u.col2, ..   -- You have to spell out all columns!
ORDER  BY min(c.created_at)

Con PostgreSQL 9.1+ simplemente puede escribir:

GROUP  BY u.id

(como en MySQL) .. proporcionado id es la clave principal.

Cito las notas de la versión :