I'd recommend you buy a good SQL Server book and read through it. It should explain a lot of the DB performance issues to you. One thing to remember is that SQL works best when doing things in Sets vs. One-at-a-time.

First and foremost, look at where your performance is bottlenecking (SQL Profiler is where you should start out). For a 20MB database, you shouldn't be having the problems you describe.

Some things I'd suggest you look at first:
If you are doing a lot of inserts/deletes, remember that those are LOCKING the table. So SELECTs by default will wait for the LOCK (unless you are using the NOLOCK hint or set your TRANSACTION ISOLATION READ UNCOMITTED).
Are you reindexing when you insert/delete a bunch of rows (look at percentage of table as an indicator here). If you are deleting all the rows from the table regularly, think abour DROPing the table vs. DELETEs (this can help fragmentation).
Also, if you are inserting a bunch of rows into an empty database, think about dropping the non-clustered index before the inserts and then re-creating the non-clustered indexes*
If you are doing a lot of insert/deletes in a non-clustered indexed table, that will cause all sorts of page fragmentation and performance will suffer over time.

Clustered Indexes vs. Heaps:
As far as clustered indexes go, it comes down to how SQL stores things internally.

Heaps:
When you create a table without any index, it is be default a "heap". When you insert rows, it is stored internally in whatever order (typically the order it was inserted or if a deletion occurred, it can "fill in the hole").

Clustered Index:
When you create a clustered index for a table (you can only have one per table). Data is stored in the order of the primary key on the clustered index. For performance reasons, you typically want the primary key to be a unique monotonically increasing value (for example an IDENTITY column). **
So, getting back to things a little bit, depending on how WIDE your table is and how many columns you want in your result set -- having a Clustered Index SEEK in your query can be a good thing. When you seek, it will read the entire record from disk. (if you only need one or two columns and your table is 200 columns wide, then there are better options ***).

Non-Clustered Index:
A non-clustered index is like a lookup table. It stores the primary keys and then a pointer to the Clustered Index or Heap Index where the full record resides. Non-clustered indexes are where you will typically do query optimizations, but for each index you add to a table, it will slow down insert/update/delete performance (since SQL has to do more work). So it can come down to being a balancing act. Also, it is important to remember that you can have multiple columns as your key in the index. Order does matter in multi-column indexes and for performance you would want the most unique column to be first in the list (Example, city vs. state in address records).

So, lets get back to query analyzer for a second:
Ideally, you want your queries to be SEEKs and order of performance generally goes like this (best performing to lowest)
   Clustered Index Seek/Index Seek (Depending on table width and rows returned)
   Index Scan
   Clustered Index Scan
   Table Scan

Now, generally it is REALLY BAD to try and force the query to use any particular index. This goes doubly so if you don't know what you are doing. The SQL engine usually does a really good job at optimizing queries. I highly recommend not trying to use INDEX HINTS in your queries.

So, it comes down to "How do you get a query to do index seeks?"
Well, there are lots of rules around this, but a general guideline is you want your where clause to be around "=" vs. "<>".

If you think about indexes as lookup tables. It is easier to look for existence than non-existance (<> will have to look through the entire index to see if it is there thus an index scan).

Also, avoid the "OR" statement. This is almost a guaranteed index scan. If you have a WHERE clause that looks like:
WHERE LastName = 'Jones' OR LastName = 'Smith'
you might want to look at rewriting it to:
WHERE LastName IN ('Jones', 'Smith')

The LIKE statement is "Tricky".
Using LIKE 'Smith%' should result in index seeks.
Using LIKE '%Smith%' will result in an index scan.

Watch out for CONVERT/CAST
SQL can be smart about CONVERT/CAST on operators, but you can cause an index scan to occur because of them. The reason being that the CONVERTED/CAST data isn't in the index. If you use CONVERT/CAST, do it on the non-table data.
Using CONVERT(VARCHAR(30), table.dtDue) = '1/31/2008' will result in Index Scans
Using table.dtDue= CONVERT(DATETIME, '1/31/2008') will result in Index Seeks
Note: SQL can be smart about conversions.
Using table.dtDue = '1/31/2008' will also result in Index Seeks

------------------------------------

*Note: This is a quicker operation because it is working across a set of data instead of individually when the inserts occur. Another option is to do your data loading into a TEMP table and then do an INSERT from the temp table into the actual table. (Think Sets vs. Individual)

**Note: a GUID is actually a typically bad choice because it is random, not monotonically increasing causing paging issues, thus why the NewSequentialID() function was introduced for SQL 2005.

***Note: This is where a "Covered Index" comes into play. If you want to learn more, I suggest searching for that term.