All the main banks offer help and advice for start up businesses. If your relationship with your private bank is good, then they are probably the best for you. If you are straightforward with them about your business, then they can often give good advice.
I went to Barclays and got on really well with the relationship manager, and I have found them absolutely first class.
As a commercial finance broker I deal with all the main 4 plus the small ones.
I believe that you don't need any facilities (eg loans, credit cards, overdrafts) and I believe that you were looking at a food type business.
If you are receiving cash and need to pay this into a bank account then I would consider someone like Nationwide or Abbey. They will not charge you for paying cash in where as the big banks will (although most have introductory free banking periods).
If you will need facilities (now or in the future) then to be honest all the banks are pretty much the same - the most important thing is the relationship you have with your manager.
If you are going down this route then make an appointment with all the managers and find out how long they have been with the bank and how long in that position. You don't want a manager that has been there 2 months and is planning to move again soon!
Have a look at Alliance and Leicester business account. If your turnover is less than 1 million a year (which it will be as you're not VAT registered) and you pay in more than �1000 per month then all transactions are free. You can pay money in at any Post Office or Alliance and Leicester branch. The free banking will save you probably a couple of hundred pounds a year.
If you are running a food business taking in cash, then it is the banking of the cash that will be one of the more expensive charges you will incur and I agree with twenty20 that Alliance and Leicester at the moment, offers the best rates for business banking. Best of luck.