Performance improvement with lots of rows (1,000,000 + records)

Below is a table and some of the queries that I run take a lot of time (10-40 seconds). What indexes should I add to improve performance without making the table too large. I was also told that if I use "abc%" for my similar queries, I can use the index. It's true?

phppos_items

+-----------------------+--------------+------+-----+---------+----------------+
| Field                 | Type         | Null | Key | Default | Extra          |
+-----------------------+--------------+------+-----+---------+----------------+
| name                  | varchar(255) | NO   |     | NULL    |                |
| category              | varchar(255) | NO   |     | NULL    |                |
| supplier_id           | int(11)      | YES  | MUL | NULL    |                |
| item_number           | varchar(255) | YES  | UNI | NULL    |                |
| description           | varchar(255) | NO   |     | NULL    |                |
| cost_price            | double(15,2) | NO   |     | NULL    |                |
| unit_price            | double(15,2) | NO   |     | NULL    |                |
| quantity              | double(15,2) | NO   |     | 0.00    |                |
| reorder_level         | double(15,2) | NO   |     | 0.00    |                |
| location              | varchar(255) | NO   |     | NULL    |                |
| item_id               | int(10)      | NO   | PRI | NULL    | auto_increment |
| allow_alt_description | tinyint(1)   | NO   |     | NULL    |                |
| is_serialized         | tinyint(1)   | NO   |     | NULL    |                |
| deleted               | int(1)       | NO   |     | 0       |                |
+-----------------------+--------------+------+-----+---------+----------------+

#checking if item exists
SELECT * FROM (`phppos_items`) WHERE `item_id` = 1

#Get all offset + limit, can take 20+ seconds, take longer as offset gets bigger
SELECT * FROM (`phppos_items`) WHERE `deleted` = 0 ORDER BY `name` asc LIMIT 16, 16

#Count all non deleted, haven't tested yet bug I would imagine it would take awhile as deleted is not indexed
SELECT * FROM (`phppos_items`) WHERE `deleted` = 0

#Filtering, haven't tested yet, but I would guess it would take a while as there are no indexes on any of these fields
SELECT * FROM (`phppos_items`) WHERE `quantity` <= reorder_level AND `is_serialized` = 1 AND `description` = '' AND `deleted` = 0 ORDER BY `name` asc

#Get info about a particular item. This is pretty fast
SELECT * FROM (`phppos_items`) WHERE `item_id` = 1

#Get info about an item based on item_number, this seems pretty fast
SELECT * FROM (`phppos_items`) WHERE `item_number` = '1234'

#Search queries, very slow
SELECT * FROM (`phppos_items`) WHERE `deleted` = 0 AND `name` LIKE '%abc%' ORDER BY `name` asc
SELECT DISTINCT `category` FROM (`phppos_items`) WHERE `deleted` = 0 AND `category` LIKE '%abc%' ORDER BY `category` asc
SELECT * FROM (`phppos_items`) WHERE `deleted` = 0 AND `item_number` LIKE '%abc%' ORDER BY `item_number` asc
SELECT * FROM (`phppos_items`) WHERE `deleted` = 0 AND `name` LIKE '%abc%' ORDER BY `name` asc
SELECT * FROM (`phppos_items`) WHERE `deleted` = 0 AND `item_number` LIKE '%abc%' ORDER BY `item_number` asc
SELECT * FROM (`phppos_items`) WHERE (name LIKE '%abc%' or item_number LIKE '%abc%' or category LIKE '%abc%') and deleted=0 ORDER BY `name` asc LIMIT 16

#Category search, pretty fast
SELECT DISTINCT `category` FROM (`phppos_items`) WHERE `deleted` = 0 AND `category` LIKE '%abc%' ORDER BY `category` asc

#Get Categories, pretty fast
SELECT DISTINCT `category` FROM (`phppos_items`) WHERE `deleted` = 0 ORDER BY `category` asc