Soy uruguayo, ¿Qué me conviene más para regularizar mi situación en España?

En caso de que estés ya empadronado desde hace más de seis meses (al menos desde el mes de octubre, para que pudieras presentar la solicitud de Permiso de Trabajo en abril) según lo que están diciendo en televisión debes tener el empadronamiento de más de 6 meses y que alguien te quiera contratar por 6 meses. De momento no han especificado más requisitos y hasta que no se apruebe el reglamento de extranjería nuevo no se puede asegurar nada.
Si te casas con española, ten en cuenta que en el registrro civil os hacen una entrevista para verificar que va a ser un matrimonio legal y no de conveniencia. En caso de que tuvieras novia española y te vayas a casar, una vez casados tendrías que ir a Uruguay o al ultimo país de residencia (menos España) y pedir visado como cónyuge de española presentando copia de la partida de matrimonio española, DNI de tu esposa, certificado de antecedentes penales y medico, etc. (No obstante este requisito ha estado cambiando continuamente, por lo que te aconsejo que antes de hacer el viaje hastta Uruguay verifiques si te van a exigir el visado en España)
Una vez te conceden el visado (alrededor de un mes) entras en España y solicitas Tarjeta de residencia comunitaria presentando la misma documentación que en el consulado y con el visado. Con esa tarjeta puedes trabajar o no. Dura 5 anos y no es necesario presentar ninguna documentación de una empresa. En tres meses tienes la tarjeta desde que la pides.