Encontrando registros únicos, ordenados por campo em associação, com PostgreSQL e Rails 3?

A consulta que você está procurando deve ser semelhante a esta:

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)

Você pode participar da tabela user se você precisa de colunas dessa tabela no resultado, senão você nem precisa para a consulta.
Se você não precisa de min_created_at no SELECT lista, você pode simplesmente deixá-la de lado.

Deve ser fácil de traduzir para Ruby (no qual não sou bom).

Para obter o registro completo do usuário (como deduzo do seu comentário):

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

Ou:

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)

Com o PostgreSQL 9.1+ você pode simplesmente escrever:

GROUP  BY u.id

(como no MySQL) .. fornecido id é a chave primária.

Cito as notas de versão :