Contact me if you need a recommendation. I can point you to good security consultants probably within your budget.
Any idea how much can such a service cost, assuming web application with a very common stack (such as Ruby on Rails + PostgreSQL)? Is it something like $5k, $10k, or $20k+? Or it really depends? Sorry if it's a very amateur question, I have no experience in dealing with such companies so have no clue how much can it cost.
Security is not cheap.
Disclaimer: worked for such company.