They would be required to help us brand our new company
Heard enough already - jeeze, a new company? Branding will eat that 25k so fast, you won't see squat. ROI advertising/PR is what you want to begin with and suggest you start with Public Relations and do most of this yourself!
If you can't hack the idea or dont have the time, a good small PR agency can do something for 7-10k and drum up some nice PR editorial stuff that will do more good than brand advertising ever will.
PR - the DIY approach
Begin with a press release, send this to ALL local newspapers and speak to the Journalists PERSONALLY!, see what you get back (usually its small mentions for off-line biz types) - put stories in your website, then contact some regionals and test that. This can take 2 months before anything is printed or you see any results.
Paid Links on Main industry targeted portals
Get these in the hundreds. You want lots of little links and adverts in as many places as possible. Make a list of related PORTALS , and contact the owners for the rate card. Your aim is to get on mid-range to high traffic sites, and for £5'000, you want 25 to 50 links, maybe some homepage spots for that if you can bargain well.
Do this yourself - you don't need an agency to plug your own biz - UNLESS the agency happen to own the main industry portals for your sector..... which I very much doubt as they won't be that clever, or they'd have thought of that idea in the first place.
Paid Links on targeted 3rd Tier portals
Copy the above - these are related lower-rated portals who will give a link for a small fee eg: £25 a year etc. Aim for 300 of these (depending on the sector). Idea is to grab quick-targeted traffic-flow/Fixed link presense for ROI sales - eg: 100 to 150 visitors per year is considered good for these sites.
Email/Newsletter marketing
Start building a list of 3000 businesses to contact. Obviously actual clients is best, but that's a long-term goal and takes time. Build a content, regular e-zine kind of offering and send it out for free. Once your content is settled on, add a sign-up page and build up a list.
Seek out other websites ezines, these can be low-cost and great to get your name out there. Plus if you find a few, then list who you use on your website.